《算法分析习题课 第六章》由会员分享，可在线阅读，更多相关《算法分析习题课 第六章（36页珍藏版）》请在装配图网上搜索。
1、算法分析习题选讲(第六章)第六章 1011 Lennys Lucky Lotto 1121 Tri Tiling 1264 Atomic Car Race 1828 Minimal 1527 Tiling a Grid With Dominoes 1148 过河 1176 Two Ends 1163 Tour 1345 能量项链 1687 Permutation1011 Lennys Lucky Lotto 给出N和M，问有多少个长度为N的序列，使得每个数的范围都在1,M之间，并且序列中每一个数至少是前一个数的两倍。解题思路 dpij表示考虑前i位且第i位为j的方案。先枚举位数i，再枚举最后一
2、个数j，最后统计k。时间复杂度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 b
3、（假设在最后一个位置换轮胎，但这一次换轮胎是没必要的）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=109 1=S=T=10 1=M=100解题
4、思路 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+)max=101;for(j=i-t;j=0)i
5、f(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,dataj+fij-1);1163 Tour 有一个人要
6、从起点开始经过所有目的地再回到起点。他只能从起点（最左端的点），向右一直到达最右端的点，再返回起点，在这一次往返要经过所有的点。求最短路程。解题思路 一次往返可以看作从最左端点到最右端点的两条独立路径。对所有点按从左到右排序后，用dpij表示两条路径现在分别在i和j点。假设ij，则现在轮到枚举第i+1个点，则可以从i到达第i+1个点，也可以j到达第i+1个点。1345 能量项链 给出一串项链，每次可以选相邻两个珠子进行聚合，释放出一定的能量，并产生一个新珠子。项链是头尾相接的。求释放的能量的总和的最大值。项链长度不超过100。解题思路 每次聚合，都会使数字中一的个数字消失。动态规划，状态为i,
7、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 Permutation n个数的排列，可以在中间插入小于号和大于号，如1 3 5 4 2 变成 1342。现在问n个数其中有k个小于号的排列有多少个。n,k=100解题思路 用dpij表示i个数的排列有j个小于号，现在要扩展到i+1个数的排列，即插入一个数要大于当前所有数。当这个数插入位置为序列头或小于号中间时，排列比原来多出一个大于号。当这个数插入位置为序列尾或大于号中间时，排列比原来多出一个小于号。
算法分析习题课 第六章
