一.最小难度 小Q和牛博士合唱一首歌曲,这首歌曲由n个音调组成,每个音调由一个正整数表示。 对于每个音调要么由小Q演唱要么由牛博士演唱,对于一系列音调演唱的难度等于所有相邻音调变化幅度之和, 例如一个音调序列是8, 8, 13, 12, 那么它的难度等于|8 - 8| + |13 - 8| + |12 - 13| = 6(其中||表示绝对值)。 现在要对把这n个音调分配给小Q或牛博士,让他们演唱的难度之和最小,请你算算最小的难度和是多少。 如样例所示: 小Q选择演唱{5, 6}难度为1, 牛博士选择演唱{1, 2, 1}难度为2,难度之和为3,这一个是最小难度和的方案了。
输入描述: 输入包括两行,第一行一个正整数n(1 ≤ n ≤ 2000) 第二行n个整数v[i](1 ≤ v[i] ≤ 10^6), 表示每个音调。
输出描述: 输出一个整数,表示小Q和牛博士演唱最小的难度和是多少。
示例1 输入 5 1 5 6 2 1 输出 3
思路： 对于每一个音调，想要知道其让小Q唱的代价高还是让牛博士唱的代价高，都必须知道小Q或牛博士唱的最后一个音调，假设为第i和第j个，另dp[i][j]为小Q唱最后唱到第i个音调和牛博士最后唱到第j个音调的最小难度，由于无论小Q最后唱第i个音牛博士最后唱第j个音还是牛博士最后唱第i个音小Q唱第j个音，其最小代价是不变的，因此有dp[i][j]==dp[j][i]。
现在规定i>j。我们考虑d[i][j],现在第i个音调是要加入到小Q或牛博士唱的序列上，显然，需要知道小Q和牛博士最后唱的音调，如果小Q最后唱第i-1个音调，那么牛博士最后唱第j个音调就会有： j小于i-1，再假设小Q唱第i个音调，则dp[i][j]=dp[i-1][j]+abs(v[i]-v[i-1])。(这种情况与牛博士唱第i-1个音调小Q唱第j个音调相同)。或者小Q最后唱了第i-1个音调，牛博士最后唱了第j个音调，但第i个音调由牛博士唱，我们不知道牛博士要从哪里唱，才能使得牛博士唱第i个音调时，使得代价最小，因此有： dp[i-1][i]=min(dp[i-1][k]+abs(v[i]-v[k])),k=0,1,2,…,i-2。 由于之前已经规定i>j，且dp[i][j]==dp[j][i]，故改成： dp[i][i-1]=min(dp[i-1][k]+abs(v[i]-v[k])),k=0,1,2,…,i-2。
但是dp[i][i-1]无法表示小Q唱第i个音调而牛博士唱前面的第0到i-1个音调，因此需要初始化d[i][i-1]为这种情况的代价，最后一起比较
时间复杂度为O(n^2) 代码如下(还能再比较上进行优化)：
def findMinDifficulty(nums): n=len(nums) if n<=2: return 0 dp=[[0]*n for _ in range(n)] #初始化d[i][i-1] for i in range(2,n): dp[i][i-1]=dp[i-1][i-2]+abs(nums[i-1]-nums[i-2]) for i in range(2,n): #可优化比较方式 if j<i-1: dp[i][j]=dp[i-1][j]+abs(nums[i]-nums[i-1]) else: choices=[dp[i-1][k] + abs(nums[i] - nums[k]) for k in range(i - 1)] choices.append(dp[i][j]) dp[i][j]=min(choices) return min(dp[n-1][:-1])二.疯狂队列
小易老师是非常严厉的,它会要求所有学生在进入教室前都排成一列,并且他要求学生按照身高不递减的顺序排列。有一次,n个学生在列队的时候,小易老师正好去卫生间了。学生们终于有机会反击了,于是学生们决定来一次疯狂的队列,他们定义一个队列的疯狂值为每对相邻排列学生身高差的绝对值总和。由于按照身高顺序排列的队列的疯狂值是最小的,他们当然决定按照疯狂值最大的顺序来进行列队。现在给出n个学生的身高,请计算出这些学生列队的最大可能的疯狂值。小易老师回来一定会气得半死。 输入描述: 输入包括两行,第一行一个整数n(1 ≤ n ≤ 50),表示学生的人数 第二行为n个整数h[i](1 ≤ h[i] ≤ 1000),表示每个学生的身高
输出描述: 输出一个整数,表示n个学生列队可以获得的最大的疯狂值。
如样例所示: 当队列排列顺序是: 25-10-40-5-25, 身高差绝对值的总和为15+30+35+20=100。 这是最大的疯狂值了。 示例1 输入 5 5 10 25 40 25 输出 100
思路：贪心算法。将输入身高h进行排序，定义一个双向队列，以最大值为第一个元素。对身高h序列有两个指针，h_left初始化指向下标为0的元素，h_right指向下标为n-2的元素，两个指针分别向中间靠拢。left,right是双向队列左边第一个元素和右边第一个元素的值。left,right分别与h_left,h_right比较，取最大值放置在队列的相应一侧，即可求出最大高度差的序列。
代码：
n=int(raw_input()) h=[int(x) for x in raw_input().split(' ')] h.sort() h_left,h_right=0,n-2 s=0 left,right=h[-1],h[-1] while h_left<=h_right: d1,d2,d3,d4=abs(left-h[h_left]),abs(left-h[h_right]),abs(right-h[h_left]),abs(right-h[h_right]) if d1==max(d1,d2,d3,d4): left=h[h_left] h_left+=1 s+=d1 elif d2==max(d1,d2,d3,d4): left=h[h_right] h_right-=1 s+=d2 elif d3==max(d1,d2,d3,d4): right=h[h_left] h_left+=1 s+=d3 elif d4==max(d1,d2,d3,d4): right=h[h_right] h_right-=1 s+=d4 print s三.堆棋子
小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.
输入描述: 输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数 第二行为n个棋子的横坐标x[i](1 ≤ x[i] ≤ 10^9) 第三行为n个棋子的纵坐标y[i](1 ≤ y[i] ≤ 10^9)
输出描述: 输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格
如样例所示: 对于1个棋子: 不需要操作 对于2个棋子: 将前两个棋子放在(1, 1)中 对于3个棋子: 将前三个棋子放在(2, 1)中 对于4个棋子: 将所有棋子都放在(3, 1)中 示例1 输入 4 1 2 4 9 1 1 1 1 输出 0 1 3 10
基本思路：暴力破解。任意一个格子有i个棋子即可。若选出i个棋子，使其移动操作最小的格子必然在这i个棋子的所有x和y之间选出候选点x*,y*。容易知道，移动x轴和移动y轴相互独立，互不影响。故遍历每个候选的x,y值，组成n*n个点，分别计算其与实质坐标点的距离，取前k个距离最近的点，选出n*n个点前k个距离最近点之和的最小值作为一个格子最少有k个棋子的解即可。
代码：
n=int(raw_input()) x=[int(i) for i in raw_input().split(' ')] y=[int(i) for i in raw_input().split(' ')] def distence(p1,p2): return abs(p1[0]-p2[0])+abs(p1[1]-p2[1]) ans=[float('inf')]*n for i in range(n): for j in range(n): p1=(x[i],y[j]) dis_arr=[] for k in range(n): p2=(x[k],y[k]) dis=distence(p1,p2) dis_arr.append(dis) dis_arr.sort() for k in range(n): ans[k]=min(ans[k],sum(dis_arr[:k+1])) print ' '.join([str(a) for a in ans])