算法分析习题课 第六章

1、算法分析习题选讲(第六章)第六章1011 Lennys Lucky Lotto1121 Tri Tiling1264 Atomic Car Race1828 Minimal1527 Tiling a Grid With Dominoes1148 过河1176 Two Ends1163 Tour1345 能量项链1687 Permutation1011 Lennys Lucky Lotto给出N和M，问有多少个长度为N的序列，使得每个数的范围都在1,M之间，并且序列中每一个数至少是前一个数的两倍。解题思路dpij表示考虑前i位且第i位为j的方案。先枚举位数i，再枚举最后一个数j，最后统计k。时间

2、复杂度O(N*M*M)。1121 Tri Tiling用1*2的长方形铺满3*n的长方形，有多少种方法。解题思路定义如图几种缺口状态。012345状态转移0 - 51 - 32 - 43 - 52 - 55 - 35 - 25 - 04 - 23 - 5初始第0列是状态0终止第n+1列是状态51264 Atomic Car Race在一次赛车比赛中，在检查点换轮胎需要花费一定时间，而速度与离上一次换轮胎的路程相关，问从起点到终点的最少时间。解题思路先求出从换完轮胎到走每个距离段所用的时间dpij表示到达第i个换轮胎点，上一次换轮胎位置是j时的消耗值初始状态有dp10, dp11答案为 dpnn

3、 b（假设在最后一个位置换轮胎，但这一次换轮胎是没必要的）1828 Minimal给出两个集合S1，S2，在S2中选出一些不重复的数与S1每个数匹配，使得匹配的数的差的绝对值尽量小。集合中数的个数不超过500。解题思路首先证明，在S1中取两个数a1,b1，在S2中取两个数a2,b2，若a1b1,a2b2，则|a1-a2|+|b1-b2|1, 0-2, 0-3, 0-5, 1-2, 1-0, 2-1, 2-0, 3-0, 3-4, 4-3, 5-0, 0-01148 过河桥的起点为0，终点为L，其中地有M个石子。青蛙每次跳的范围为S,T，问要跳过桥最小踩到石子次数。1 = L = 1091 =

4、S = T = 101 = M = 100解题思路L的值大太，直接按L的值进行动态规划不可行。分情况：若S和T相等，则踩到的石子数是固定的；若S和T不相等，因为S和T的最大值为10，所以当两个石子相差太远是没有意义的，这里取的值为90，当石子距离相差90以上时，看作90，答案不变。压缩后桥长度不超过10000，直接动态规划即可。for(i=0;i90)deltai=90;for(i=1;i=m;i+)rocki=rocki-1+deltai-1;for(i=1;i=m;i+)dprocki=1;f0=1;work();void work() L=rockm+90;for(i=s;i=L;i+)

5、 max=101;for(j=i-t;j=0)if(fj&dpj+dpimax) max=dpj+dpi;fi=1;dpi=max;1176 Two Ends两个人轮流从一列数中取数，只能从两端取。第一个人可以用任意策略，第二个人贪心每次取最大的数。一个人的分数等于他取的数的总和。问分数差值最大为多少。n=dataj) fij=-datai+fi+1j; else fij=-dataj+fij-1;for(i=0;i=0;i-)for(j=i+1;j=dataj) fij=-datai+fi+1j; else fij=-dataj+fij-1;else fij=max(datai+fi+1j,

6、dataj+fij-1);1163 Tour有一个人要从起点开始经过所有目的地再回到起点。他只能从起点（最左端的点），向右一直到达最右端的点，再返回起点，在这一次往返要经过所有的点。求最短路程。解题思路一次往返可以看作从最左端点到最右端点的两条独立路径。对所有点按从左到右排序后，用dpij表示两条路径现在分别在i和j点。假设ij，则现在轮到枚举第i+1个点，则可以从i到达第i+1个点，也可以j到达第i+1个点。1345 能量项链给出一串项链，每次可以选相邻两个珠子进行聚合，释放出一定的能量，并产生一个新珠子。项链是头尾相接的。求释放的能量的总和的最大值。项链长度不超过100。解题思路每次聚合，

7、都会使数字中一的个数字消失。动态规划，状态为i,j表示从i开始，按顺时针方向到j，这一段珠子所聚合得到的能量最大值。状态转移，要求出i,j的值，则存在一个k在i和j之间，i,j的值为i,k的值与k+1,j的值与这次聚合所释放出的能量的总和，取最大值。且长度较大的区间需要长度较小的区间得到，因此枚举顺序为区间的长度从小到大。for (step=1;stepn;step+) for (i=0;i=n*2) break; for (k=i;kj;k+) temp=ansik+ansk+1j +ai*ak+1*aj+1; if (ansijtemp) ansij=temp; 1687 Permutationn个数的排列，可以在中间插入小于号和大于号，如1 3 5 4 2 变成 1342。现在问n个数其中有k个小于号的排列有多少个。n,k=100解题思路用d