[普及组]动态规划经典题目分析.ppt

《[普及组]动态规划经典题目分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划经典题目分析中山纪念中学陈启峰一般步骤确定状态：状态的参数一般有1）描述位置的：前(后)i单位，第i到第j单位，坐标为(i,j)等2）描述数量的：取i个，不超过i个，至少i个等3）描述对后有影响的：状态压缩的，一些特殊的性质一般步骤转移方程：1）检查参数是否足够；2）分情况：最后一次操作的方式，取不取，怎么样放，前一项是什么3）初始条件是什么。4）注意无后效性。比如说，求A就要求Ｂ，求Ｂ就要求Ｃ，而求Ｃ就要求Ａ，这就不符合无后效性了。一般步骤编程实现方式1）递推2）记忆化搜索（一般在状态的拓朴顺序不很明确时使用）一般步骤恰当地使用数据可以使动态规划的时间复杂度降下。队列——O(n^

2、2*??)O(n*??)线段树、堆、二叉查找树——O(n*??)O(logn*??)Hash表、并查集——O(n*??)O(??)此外运用四边行不等式可以使O(n^3*??)O(n^2*??)经典题最长公共子序列最长上升子序列最优二分检索树最优矩阵链乘最优三角剖分任务调度问题叠放箱子【问题】某港口有一批箱子，将其编号，分别为1至N。每一个箱子的尺寸规格是一样的，现在要将其中某些箱子叠放起来，箱子叠放的规则如下：一、每个箱子上最多只能直接叠放一个箱子；二、编号较小的箱子不能放在编号较大的箱子之上；三、每个箱子都给出了自身重量与可承受重量，每个箱子之上的所有箱子重量之和不得超过该箱的可

3、承受重量。为了节约堆放场地，希望你编程从中选出最多个箱子，使之能够在满足条件的情况下叠放起来。【输入】第一行是一个整数N（1≤N≤1000）。以下共有N行，每行两个整数，中间以空格分隔，分别表示每个箱子的自身重量与可承受重量，两个数值均为小于等于3000的正整数。【输出】第一行应当输出最多可叠放的箱子总数M。【样例】有五个箱子，如下表：编号自身重量可承受重量119152713357468512则最多可以叠放4个箱子，方案之一如：1、2、3、5分析设F[i,j]表示第i个箱子到第N个箱子中总重量为j的最大箱子数。考虑第i个箱子放与不放的情况。注意，能选的条件是j≥weight[i]并且cap

4、acity≥j-weight[i]代码programCQF_BOX;usesmath;constmaxn=1000;varweight,capacity:array[1..maxn]oflongint;f:array[1..maxn+1,0..6000]oflongint;n:longint;procedureinit;vari:longint;beginreadln(n);fori:=1tondoreadln(weight[i],capacity[i]);end;procedurework;vari,j,ans:longint;beginfillchar(f,sizeof(f),200)

5、;f[n+1,0]:=0;fori:=ndownto1doforj:=0to6000dobeginf[i,j]:=f[i+1,j];if(j>=weight[i])and(capacity[i]>=j-weight[i])thenf[i,j]:=max(f[i,j],f[i+1,j-weight[i]]+1);end;ans:=0;fori:=0to6000doans:=max(ans,f[1,i]);writeln(ans);end;CMI给出一个1到n的排列，每次可以移动一个数到一个任意位置。问要达到状态1,2,3……n至少移动多少次？SampleInput521453SampleOu

6、tput2分析答案就是N减去这个排列的最长上升子序列的长度lis。为什么呢？证明必要性：一次移动就相当于删除一个数并添加上这个数。删除一个数不会增加lis。添加一个数最多使lis加1。因此一次移动最多可以使lis加1要达到目标状态至少要N-lis次移动。证明充分性：每次选取一个非lis上的一个数，并将它移动到lis上合适的位置。也就是说，将它移动到lis上前比它小，后比它大的位置。算法运用动态规划：F[i]表示以第i个数为结束的最长上升子序列的长度。F[i]=max{F[j]+1

7、value[j]

8、好的方法呢？算法建立一个数组last。Last[i]表示长度为i的子序列中最小的最后一个数。特别的last[0]=负无穷假如现在已经处理了前i-1个数，考虑加入第i个数。算法如果last[lis]