算法分析与设计课件：习题选讲第六章bywxyz

习题选讲,赵浩泉wxyz202soj.me,2011-12-29,2,第六章,1011LennysLuckyLotto1121TriTiling1264AtomicCarRace1828Minimal1527TilingaGridWithDominoes1148过河1176TwoEnds1163Tour1345能量项链1687Permutation,2011-12-29,3,1011LennysLuckyLotto,题目大意：给出N和M，问有多少个长度为N的序列，使得每个数的范围都在1,M之间，并且序列中每一个数至少是前一个数的两倍。,2011-12-29,4,1011LennysLuckyLotto,解题思路：dpij表示考虑前i位且第i位为j的方案。dpij=sumdpi-1k|1=k=j/2先枚举位数i，再枚举最后一个数j，最后统计k。时间复杂度O(N*M*M)。,2011-12-29,5,1011LennysLuckyLotto,for(j=1;j=2000;j+)dp1j=1;for(i=2;i=10;i+)for(j=1;j=2000;j+)dpij=0;for(k=1;k*2=j;k+)dpij+=dpi-1k;,2011-12-29,6,1121TriTiling,题目大意：用1*2的长方形铺满3*n的长方形，有多少种方法。,2011-12-29,7,1121TriTiling,解题思路：定义如图几种缺口状态。,0,1,2,3,4,5,2011-12-29,8,1121TriTiling,状态转移：,2011-12-29,9,1121TriTiling,状态转移：,2011-12-29,10,1121TriTiling,初始第0列是状态0，终止第n+1列是状态5。dp00=1;for(i=1;i=n+1;i+)dpi5+=dpi-10;dpi3+=dpi-11;dpi4+=dpi-12;dpi5+=dpi-12;dpi1+=dpi-13;dpi5+=dpi-13;dpi2+=dpi-14;dpi3+=dpi-15;dpi2+=dpi-15;dpi0+=dpi-15;,2011-12-29,11,1264AtomicCarRace,题目大意：在一次赛车比赛中，在检查点换轮胎需要花费一定时间，而速度与离上一次换轮胎的路程相关，问从起点到终点的最少时间。,2011-12-29,12,1264AtomicCarRace,解题思路：先求出从换完轮胎到走每个距离段所用的时间。d0=0;for(i=0;ian;i+)if(ir)temp=1/(v-f*(r-i);elsetemp=1/(v-e*(i-r);di+1=di+temp;,2011-12-29,13,1264AtomicCarRace,再给出每两个检查点（包括起点）之间的用时。for(i=0;in;i+)for(j=i+1;j=n;j+)cij=daj-ai;,2011-12-29,14,1264AtomicCarRace,再用递归的方法进行动态规划。dpij=mincij,dpik+dpkj+b|ikj,2011-12-29,15,1264AtomicCarRace,doublecal(ints,intt)if(visitedst)returndpst;visitedst=true;dpst=cst;for(inti=s+1;it;i+)doubletemp=cal(s,i)+cal(i,t)+b;if(tempdpst)dpst=temp;returndpst;,2011-12-29,16,1828Minimal,题目大意：给出两个集合S1，S2，在S2中选出一些不重复的数与S1每个数匹配，使得匹配的数的差的绝对值尽量小。集合中数的个数不超过500。,2011-12-29,17,1828Minimal,解题思路：首先证明，在S1中取两个数a1,b1，在S2中取两个数a2,b2，若a1b1,a2b2，则|a1-a2|+|b1-b2|a1-b2|+|a2-b1|。即对于已排序的S1的数，只会按顺序对应已排序的S2的数。dpij表示S1中前i个数与S2中前j个数匹配时，第i个数或之前的匹配数值差的绝对值之和。,2011-12-29,18,1828Minimal,sort(s1,s1+n);sort(s2,s2+m);dp00=abs(s10-s20);for(i=1;im;i+)dp0i=min(dp0i-1,abs(s10-s2i);for(i=1;i2,0-3,0-5,1-2,1-0,2-1,2-0,3-0,3-4,4-3,5-0,0-0,2011-12-29,21,1527TilingaGridWithDominoes,dp00=1;for(i=1;i=n+1;i+)dpi0+=dpi-10;dpi1+=dpi-10;dpi2+=dpi-10;dpi3+=dpi-10;dpi5+=dpi-10;dpi2+=dpi-11;dpi0+=dpi-11;dpi1+=dpi-12;dpi0+=dpi-12;dpi0+=dpi-13;dpi4+=dpi-13;dpi3+=dpi-14;dpi0+=dpi-15;,2011-12-29,22,1148过河,题目大意：桥的起点为0，终点为L，其中地有M个石子。青蛙每次跳的范围为S,T，问要跳过桥最小踩到石子次数。1=L=1091=S=T=101=M=100,2011-12-29,23,1148过河,解题思路：L的值大太，直接按L的值进行动态规划不可行。分情况：若S和T相等，则踩到的石子数是固定的；若S和T不相等，因为S和T的最大值为10，所以当两个石子相差太远是没有意义的，这里取的值为90，当石子距离相差90以上时，看作90，答案不变。压缩后桥长度不超过10000，直接动态规划即可。,2011-12-29,24,1148过河,for(i=0;i90)deltai=90;for(i=1;i=m;i+)rocki=rocki-1+deltai-1;for(i=1;i=ar)returndplr=cal(l+1,r)-al;elsereturndplr=cal(l,r-1)-ar;elsereturndplr=max(cal(l+1,r)+al,cal(l,r-1)+ar);,2011-12-29,29,1163Tour,题目大意：有一个人要从起点开始经过所有目的地再回到起点。他只能从起点（最左端的点），向右一直到达最右端的点，再返回起点，在这一次往返要经过所有的点。求最短路程。,2011-12-29,30,1163Tour,解题思路：一次往返可以看作从最左端点到最右端点的两条独立路径。对所有点按从左到右排序后，用dpij表示两条路径现在分别在i和j点。假设ij，则现在轮到枚举第i+1个点，则可以从i到达第i+1个点，也可以j到达第i+1个点。,2011-12-29,31,1163Tour,for(i=0;ij)if(i-1j)dpij=dpi-1j+di-1i;elsefor(k=0;ktemp)dpij=temp;elseif(ji)/*similarto(ij)*/,2011-12-29,32,1345能量项链,题目大意：给出一串项链，每次可以选相邻两个珠子进行聚合，释放出一定的能量，并产生一个新珠子。项链是头尾相接的。求释放的能量的总和的最大值。项链长度不超过100。,2011-12-29,33,1345能量项链,解题思路：每次聚合，都会使数字中一的个数字消失。动态规划，状态为i,j表示从i开始，按顺时针方向到j，这一段珠子所聚合得到的能量最大值。状态转移，要求出i,j的值，则存在一个k在i和j之间，i,j的值为i,k的值与k+1,j的值与这次聚合所释放出的能量的总和，取最大值。且长度较大的区间需要长度较小的区间得到，因此枚举顺序为区间的长度从小到大。,2011-12-29,34,1345能量项链,for(step=1;step=n*2)break;for(k=i;kj;k+)temp=ansik+ansk+1j+ai*ak+1*aj+1;if(ansij2。现在问n个数其中有k个小于号的排列有多少个。n,k=100,2011-12-29,36,1687Permutation,解题思路：用dpij表示i个数的排列有j个小于号，现在要扩展到i+1个数的排列，即插入一个数要大于当前所有数。当这个数插入位置为序列头或小于号中间时，排列比原来多出一