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

习题选讲习题选讲赵浩泉赵浩泉2011-12-291第六章第六章n1011 Lennys Lucky Lotton1121 Tri Tilingn1264 Atomic Car Racen1828 Minimaln1527 Tiling a Grid With Dominoesn1148 过河过河n1176 Two Endsn1163 Tourn1345 能量项链能量项链n1687 Permutation2011-12-2921011 Lennys Lucky Lotton题目大意：题目大意：n给出给出N和和M，问有多少个长度为，问有多少个长度为N的序列，的序列，使得每个数的范围都在使得每个数的范围都在1,M之间，并且序之间，并且序列中每一个数至少是前一个数的两倍。列中每一个数至少是前一个数的两倍。2011-12-2931011 Lennys Lucky Lotton解题思路：解题思路：ndpij表示考虑前表示考虑前i位且第位且第i位为位为j的方案。的方案。ndpij=sumdpi-1k|1=k=j/2n先枚举位数先枚举位数i，再枚举最后一个数，再枚举最后一个数j，最后统，最后统计计k。n时间复杂度时间复杂度O(N*M*M)。2011-12-2941011 Lennys Lucky Lottonfor(j=1;j=2000;j+)ndp1j=1;nfor(i=2;i=10;i+)nfor(j=1;j=2000;j+)ndpij=0;nfor(k=1;k*2 51-32-43-52-52011-12-2981121 Tri Tilingn状态转移：状态转移：5-35-25-04-23-52011-12-2991121 Tri Tilingn初始第初始第0列是状态列是状态0，终止第，终止第n+1列是状态列是状态5。ndp00=1;nfor(i=1;i=n+1;i+)ndpi5+=dpi-10;ndpi3+=dpi-11;ndpi4+=dpi-12;ndpi5+=dpi-12;ndpi1+=dpi-13;ndpi5+=dpi-13;ndpi2+=dpi-14;ndpi3+=dpi-15;ndpi2+=dpi-15;ndpi0+=dpi-15;n2011-12-29101264 Atomic Car Racen题目大意：题目大意：n在一次赛车比赛中，在检查点换轮胎需要在一次赛车比赛中，在检查点换轮胎需要花费一定时间，而速度与离上一次换轮胎花费一定时间，而速度与离上一次换轮胎的路程相关，问从起点到终点的最少时间。的路程相关，问从起点到终点的最少时间。2011-12-29111264 Atomic Car Racen解题思路：解题思路：n先求出从换完轮胎到走每个距离段所用的时间。先求出从换完轮胎到走每个距离段所用的时间。nd0=0;nfor(i=0;ian;i+)nnif(ir)ntemp=1/(v-f*(r-i);nelsentemp=1/(v-e*(i-r);ndi+1=di+temp;n2011-12-29121264 Atomic Car Racen再给出每两个检查点（包括起点）之间的再给出每两个检查点（包括起点）之间的用时。用时。nfor(i=0;in;i+)nfor(j=i+1;j=n;j+)ncij=daj-ai;2011-12-29131264 Atomic Car Racen再用递归的方法进行动态规划。再用递归的方法进行动态规划。ndpij=mincij,dpik+dpkj+b|ikj2011-12-29141264 Atomic Car Racendouble cal(int s,int t)nif(visitedst)nreturn dpst;nvisitedst=true;ndpst=cst;nfor(int i=s+1;it;i+)ndouble temp=cal(s,i)+cal(i,t)+b;nif(tempdpst)ndpst=temp;nnreturn dpst;n2011-12-29151828 Minimaln题目大意：题目大意：n给出两个集合给出两个集合S1，S2，在，在S2中选出一些不中选出一些不重复的数与重复的数与S1每个数匹配，使得匹配的数每个数匹配，使得匹配的数的差的绝对值尽量小。的差的绝对值尽量小。n集合中数的个数不超过集合中数的个数不超过500。2011-12-29161828 Minimaln解题思路：解题思路：n首先证明，在首先证明，在S1中取两个数中取两个数a1,b1，在，在S2中取两中取两个数个数a2,b2，若，若a1b1,a2b2，则，则|a1-a2|+|b1-b2|a1-b2|+|a2-b1|。n即对于已排序的即对于已排序的S1的数，只会按顺序对应已排序的数，只会按顺序对应已排序的的S2的数。的数。ndpij表示表示S1中前中前i个数与个数与S2中前中前j个数匹配时，个数匹配时，第第i个数或之前的匹配数值差的绝对值之和。个数或之前的匹配数值差的绝对值之和。2011-12-29171828 Minimalnsort(s1,s1+n);nsort(s2,s2+m);ndp00=abs(s10-s20);nfor(i=1;im;i+)n dp0i=min(dp0i-1,abs(s10-s2i);n for(i=1;in;i+)n dpii=dpi-1i-1+abs(s1i-s2i);n for(j=i+1;j1,0-2,0-3,0-5,1-2,1-0,2-1,2-0,3-0,3-4,4-3,5-0,0-02011-12-29201527 Tiling a Grid With Dominoesndp00=1;nfor(i=1;i=n+1;i+)ndpi0+=dpi-10;ndpi1+=dpi-10;ndpi2+=dpi-10;ndpi3+=dpi-10;ndpi5+=dpi-10;ndpi2+=dpi-11;ndpi0+=dpi-11;ndpi1+=dpi-12;ndpi0+=dpi-12;ndpi0+=dpi-13;ndpi4+=dpi-13;ndpi3+=dpi-14;ndpi0+=dpi-15;n2011-12-29211148 过河过河n题目大意：题目大意：n桥的起点为桥的起点为0，终点为，终点为L，其中地有，其中地有M个石个石子。青蛙每次跳的范围为子。青蛙每次跳的范围为S,T，问要跳过，问要跳过桥最小踩到石子次数。桥最小踩到石子次数。n1=L=109n1=S=T=10n1=M=1002011-12-29221148 过河过河n解题思路：解题思路：nL的值大太，直接按的值大太，直接按L的值进行动态规划不可行。的值进行动态规划不可行。n分情况：若分情况：若S和和T相等，则踩到的石子数是固定的；相等，则踩到的石子数是固定的；n若若S和和T不相等，因为不相等，因为S和和T的最大值为的最大值为10，所以当，所以当两个石子相差太远是没有意义的，这里取的值为两个石子相差太远是没有意义的，这里取的值为90，当石子距离相差，当石子距离相差90以上时，看作以上时，看作90，答案不，答案不变。变。n压缩后桥长度不超过压缩后桥长度不超过10000，直接动态规划即可。，直接动态规划即可。2011-12-29231148 过河过河nfor(i=0;i90)deltai=90;nnfor(i=1;i=m;i+)nrocki=rocki-1+deltai-1;nfor(i=1;i=m;i+)ndprocki=1;nf0=1;nwork();2011-12-29241148 过河过河nvoid work()nL=rockm+90;nfor(i=s;i=L;i+)nmax=101;nfor(j=i-t;j=0)nif(fj&dpj+dpimax)nmax=dpj+dpi;nfi=1;nndpi=max;nn2011-12-29251176 Two Endsn题目大意：题目大意：n两个人轮流从一列数中取数，只能从两端两个人轮流从一列数中取数，只能从两端取。第一个人可以用任意策略，第二个人取。第一个人可以用任意策略，第二个人贪心每次取最大的数。一个人的分数等于贪心每次取最大的数。一个人的分数等于他取的数的总和。问分数差值最大为多少。他取的数的总和。问分数差值最大为多少。nnr)n return 0;n if(visitedlr)n return dplr;n visitedlr=true;n if(r-l+1)%2=1)n if(al=ar)n return dplr=cal(l+1,r)-al;n elsen return dplr=cal(l,r-1)-ar;n n elsen return dplr=max(cal(l+1,r)+al,cal(l,r-1)+ar);n2011-12-29281163 Tourn题目大意：题目大意：n有一个人要从起点开始经过所有目的地再有一个人要从起点开始经过所有目的地再回到起点。他只能从起点（最左端的点），回到起点。他只能从起点（最左端的点），向右一直到达最右端的点，再返回起点，向右一直到达最右端的点，再返回起点，在这一次往返要经过所有的点。求最短路在这一次往返要经过所有的点。求最短路程。程。2011-12-29291163 Tourn解题思路：解题思路：n一次往返可以看作从最左端点到最右端点一次往返可以看作从最左端点到最右端点的两条独立路径。对所有点按从左到右排的两条独立路径。对所有点按从左到右排序后，用序后，用dpij表示两条路径现在分别在表示两条路径现在分别在i和和j点。点。n假设假设ij，则现在轮到枚举第，则现在轮到枚举第i+1个点，则可个点，则可以从以从i到达第到达第i+1个点，也可以个点，也可以j到达第到达第i+1个个点。点。2011-12-29301163 Tournfor(i=0;in-1;i+)n for(j=0;jj)n if(i-1j)n dpij=dpi-1j+di-1i;n else n for(k=0;kj;k+)n temp=dpkj+dki;n if(dpijtemp)n dpij=temp;n n n else if(ji)n /*similar to(ij)*/n n 2011-12-29311345 能量项链能量项链n题目大意：题目大意：n给出一串项链，每次可以选相邻两个珠子给出一串项链，每次可以选相邻两个珠子进行聚合，释放出一定的能量，并产生一进行聚合，释放出一定的能量，并产生一个新珠子。项链是头尾相接的。求释放的个新珠子。项链是头尾相接的。求释放的能量的总和的最大值。能量的总和的最大值。n项链长度不超过项链长度不超过100。2011-12-29321345 能量项链能量项链n解题思路：解题思路：n每次聚合，都会使数字中一的个数字消失。每次聚合，都会使数字中一的个数字消失。n动态规划，状态为动态规划，状态为i,j表示从表示从i开始，按顺时针开始，按顺时针方向到方向到j，这一段珠子所聚合得到的能量最大值。，这一段珠子所聚合得到的能量最大值。n状态转移，要求出状态转移，要求出i,j的值，则存在一个的值，则存在一个k在在i和和j之间，之间，i,j的值为的值为i,k的值与的值与k+1,j的值与这的值与这次聚合所释放出的能量的总和，取最大值。次聚合所释放出的能量的总和，取最大值。n且长度较大的区间需要长度较小的区间得到，因且长度较大的区间需要长度较小的区间得到，因此枚举顺序为区间的长度从小到大。此枚举顺序为区间的长度从小到大。2011-12-29331345 能量项链能量项链nfor(step=1;stepn;step+)n for(i=0;i=n*2)break;n for(k=i;kj;k+)n temp=ansik+ansk+1j+ai*ak+1*aj+1;n if(ansijtemp)n ansij=temp;n 2011-12-29341687 Permutationn题目大意：题目大意：nn个数的排列，可以在中间插入小于号和大个数的排列，可以在中间插入小于号和大于号，如于号，如1 3 5 4 2 变成变成 1342。现在。现在问问n个数其中有个数其中有k个小于号的排列有多少个。个小于号的排列有多少个。nn,k=1002011-12-29351687 Permutationn解题思路：解题思路：n用用dpij表示表示i个数的排列有个数的排列有j个小于号，现个小于号，现在要扩展到在要扩展到i+1个数的排列，即插入一个数个数的排列，即插入一个数要大于当前所有数。当这个数插入位置为要大于当前所有数。当这个数插入位置为序列头或小于号中间时，排列比原来多出序列头或小于号中间时，排列比原来多出一个大于号。当这个数插入位置为序列尾一个大于号。当这个数插入位置为序列尾或大于号中间时，排列比原来多出一个小或大于号中间时，排列比原来多出一个小于号。于号。2011-12-29361687 Permutationnfor(i=1;i100;i+)nfor(j=0;ji;j+)nndpi+1j+=dpij*(j+1);ndpi+1j%=2007;ndpi+1j+1+=dpij*(i-j);ndpi+1j+1%=2007;n2011-12-2937谢谢！谢谢！2011-12-2938