《算法分析习题课 第六章》由会员分享，可在线阅读，更多相关《算法分析习题课 第六章（25页珍藏版）》请在金锄头文库上搜索。
1、算法分析习题选讲(第六章)第六章1011LennysLuckyLotto1121TriTiling1264AtomicCarRace1828Minimal1527TilingaGridWithDominoes1148过河1176TwoEnds1163Tour1345能量项链1687Permutation1011LennysLuckyLotto给出N和M，问有多少个长度为N的序列，使得每个数的范围都在1,M之间，并且序列中每一个数至少是前一个数的两倍。解题思路dpij表示考虑前i位且第i位为j的方案。先枚举位数i，再枚举最后一个数j，最后统计k。时间复杂度O(N*M*M)。1121TriTili
2、ng用1*2的长方形铺满3*n的长方形，有多少种方法。解题思路定义如图几种缺口状态。012345状态转移0-51-32-43-52-55-35-25-04-23-5初始第0列是状态0终止第n+1列是状态51264AtomicCarRace在一次赛车比赛中，在检查点换轮胎需要花费一定时间，而速度与离上一次换轮胎的路程相关，问从起点到终点的最少时间。解题思路先求出从换完轮胎到走每个距离段所用的时间dpij表示到达第i个换轮胎点，上一次换轮胎位置是j时的消耗值初始状态有dp10,dp11答案为dpnnb（假设在最后一个位置换轮胎，但这一次换轮胎是没必要的）1828Minimal给出两个集合S1，S2
3、，在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=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();voidwork()L=rockm+90;for(i=s;i=L;i+)max=101;for(j=i-t;j=0)if(fj&dpj+dpimax)max=dpj+dpi;fi=1;dpi=max;
