动态规划总结课件

DP的复习与提高DP的复习与提高最长不下降子序列模型设有整数序列b1,b2,b3,……,bn,若存在i1<i2<i3<……<im,且bi1<bi2<bi3……<bim,则称b1,b2,b3,……,bn,中有长度为M的不下降序列bi1，bi2，bi3，……，bim。求序列b1,b2,b3,……,bn中所有长度（M）最大不下降序列。输入：整数序列输出：最大长度M和所有长度为M的序列个数T最长不下降子序列模型设有整数序列b1,b2,b3,……,bn分析:设h[1..n]表示n个输入的整数；令f[i]表示从第i个数开始到第m个数的最长不下降子序列的长度，则有：f[i]=max(f[j]+1)(1<=i<=n-1,i+1<=j<=n,h[i]<=h[j])边界为f[n]:=1具体求解时用倒推，fori:=n-1downto1时间复杂性：O(n2)分析:设h[1..n]表示n个输入的整数；顺推的算法设f(i)为前i个数中的最大不下降序列长度

,则f(i)=max{f(j)+1}(1<=j<i<=n,h[j]<h[i])边界为F(1)=1下面的优化算法是以顺推方向进行的.顺推的算法设f(i)为前i个数中的最大不下降序列长度,则优化如果当n<=100000时，显然上述算法要超时。从DP的基本优化思路着手，也就是去除一些一定不会有最优解产生的状态。例如：f[i]=3;h[i]=10;f[j]=3;h[j]=5,那么无论具体的搭配情况如何，状态j都要比状态i优秀。也就是说，我们只需要保留当前长度为i的序列中最后一个数字即可，并且这个数是所有长度为i的不下降序列中最后一个数的最小值。优化如果当n<=100000时，显然上述算法要超时。由此，算法的本质也发生了变化。设b[i]表示长度为i的不下降序列的最后一个元素的最小值。初始化：b[i]:=maxlongint,b[1]:=h[1]容易看出，b数组一定是不下降序列。当处理h[i]时，用二分法查找它可以连接到长度最大为多少的不下降子序列的之后（查找区间的左右边界是1~i）。假设可以连到长度最大为y的不上升子序列后，则b[y+1]:=min{b[y+1],h[i]}。在找到h[i]的最终位置后,也就知道了前i个数的最长不下降序列的长度了,这时就可记录f[i]的值.最后，b数组被赋值的元素最大下标就是问题的答案。在实现时要仔细考虑一些细节情况.由此，算法的本质也发生了变化。1.求最长不下降序列参考程序:constmaxn=100000;varh,b,f:array[1..maxn]oflongint;n,i,j,k,l,r,m:longint;found:boolean;beginreadln(n);fori:=1tondoread(h[i]);fori:=1tondob[i]:=maxlongint;b[1]:=h[1];f[1]:=1;fori:=2tondobeginl:=1;r:=i;whilel<rdobeginm:=(l+r)div2;ifb[m]<=h[i]thenl:=m+1elser:=m;end;ifb[l]>h[i]thenbeginb[l]:=h[i];f[i]:=l;end

elsef[i]:=l+1;end;j:=0;fori:=1tondoifb[i]<>maxlonginttheninc(j)elsebreak;writeln(j);fori:=1tojdowrite(b[i]:4);writeln;fori:=1tondowrite(f[i]:4);end.数据f存储了以每个元素结尾的最长不下降序列的长度.注意：两个程序的主要区别在于二分查找时对于b[m]=h[i]时的处理方法不同。对于严格递增序列来说，出现相等时，不增加序列长度。对于不降序列来说，则要增加序列长度。1.求最长不下降序列参考程序:else注意：两个程序的主要区2.求严格递增序列constmaxn=100000;varh,b,f:array[1..maxn]oflongint;n,i,j,k,l,r,m:longint;found:boolean;beginreadln(n);fori:=1tondoread(h[i]);fori:=1tondob[i]:=maxlongint;b[1]:=h[1];f[1]:=1;fori:=2tondobeginl:=1;r:=i;found:=false;whilel<=rdobeginm:=(l+r)div2;ifb[m]>h[i]thenr:=m-1elseifb[m]<h[i]thenl:=m+1elsebeginfound:=true;f[i]:=m;break;end;

end;iffound=falsethenifb[l]>h[i]thenbeginb[l]:=h[i];f[i]:=l;endelsebeginb[l+1]:=h[i];f[i]:=l+1;endend;j:=0;fori:=1tondoifb[i]<>maxlonginttheninc(j)elsebreak;writeln(j);fori:=1tojdowrite(b[i]:4);writeln;fori:=1tondowrite(f[i]:4);end.2.求严格递增序列end;最长不下降序列拓展1、求序列中最长不下降序列的个数。设t[i]为以i结尾的最长不下降序列的个数,则T[i]=∑t[j](1<=j<i<=n,h[j]<=h[i],f[i]=f[j]+1)边界为:t[1]=1当f[i]=n时，将t[i]累加举例：

h:1234658109f:123455677t:111111222答案：f=7时，个数为∑t=4最长不下降序列拓展1、求序列中最长不下降序列的个数。最长不下降序列拓展2、求本质不同的最长不下降序列的个数。(注:其实这里讨论的是单调递增序列)求本质不同的最长不下降序列个数有多少个？如：1234658109有，

12346810,12345810,1234689,1234589都是本质不同的。但对于

h12233545f12233444t11122444

答案有8个，其中4个1235，4个1234正确答案应该是两个.最长不下降序列拓展2、求本质不同的最长不下降序列的个数。(注上例显然对于原序列h中两个相同的数，重复算了多次因此，我们对算法进行改进：对原序列按h从小到大（当h[i]=h[j]时按F从大到小）排序，增设Order[i]记录新序列中的i个数在原序列中的位置。可见，求t[i]时，当f[j]=f[j+1],h[j]=h[j+1]且Order[j+1]<Order[i]时，便不累加t[j]。这样就避免了重复。

上述算法的时间复杂度为O(n2)这个算法也存在问题.对于

h12233545f12233444t11122444将得出3的错误答案如果改为统计最后结果时要求(f[i]=f[j]=maxlen)且(h[i]<>h[j]),则下面的数据又会出现错误答案:h13451235f12341234程序输出为1正确应该是2上例显然对于原序列h中两个相同的数，重复算了多次因此，我们对错误程序1:按PPT中的算法执行constmaxn=10000;varh,f,t,order:array[1..maxn]oflongint;n,i,j,k,max,mlen:longint;procedureswap(vara,b:longint);varx:longint;beginx:=a;a:=b;b:=x;end;beginreadln(n);fori:=1tondoread(h[i]);mlen:=0;fori:=1tondobeginread(f[i]);iff[i]>mlenthenmlen:=f[i];end;fori:=1ton+1doorder[i]:=i;h[n+1]:=maxlongint;f[n+1]:=mlen+1;inc(n);

错误程序1:按PPT中的算法执行fori:=1ton-1doforj:=ndowntoi+1doifh[j-1]>h[j]thenbeginswap(h[j-1],h[j]);swap(f[j-1],f[j]);swap(order[j-1],order[j]);endelseifh[j-1]=h[j]thenbeginiff[j-1]<f[j]thenbeginswap(h[j-1],h[j]);swap(f[j-1],f[j]);swap(order[j-1],order[j]);end;end;t[1]:=1;fori:=2tondoforj:=i-1downto1doif(h[j]<h[i])and(f[j]+1=f[i])thenifnot((h[j]=h[j+1])and(f[j]=f[j+1])and(order[j+1]<order[i]))theninc(t[i],t[j]);writeln(t[n]);end.fori:=1ton-1do错误程序2,按教材P224页例8-3算法constmaxn=10000;varh,f,t,order:array[1..maxn]oflongint;n,i,j,k,max,mlen:longint;procedureswap(vara,b:longint);varx:longint;beginx:=a;a:=b;b:=x;end;beginreadln(n);fori:=1tondoread(h[i]);mlen:=0;fori:=1tondobeginread(f[i]);iff[i]>mlenthenmlen:=f[i];end;fori:=1ton+1doorder[i]:=i;h[n+1]:=maxlongint;f[n+1]:=mlen+1;inc(n);fori:=1tondoiff[i]=1thent[i]:=1;fork:=2tomlen+1dofori:=ndownto1doiff[i]=kthenbeginj:=i-1;while(j>0)and(h[j]<>h[i])dobeginif(h[j]<h[i])and(f[j]+1=k)theninc(t[i],t[j]);dec(j);end;end;writeln(t[n]);end.错误程序2,按教材P224页例8-3算法fori:=1到目前通过所有数据的程序:constmaxn=10000;varh,f,t,order:array[1..maxn]oflongint;n,i,j,k,max,mlen:longint;procedureswap(vara,b:longint);varx:longint;beginx:=a;a:=b;b:=x;end;beginreadln(n);fori:=1tondoread(h[i]);mlen:=0;fori:=1tondobeginread(f[i]);iff[i]>mlenthenmlen:=f[i];end;fori:=1ton+1doorder[i]:=i;h[n+1]:=maxlongint;//建立哨兵

f[n+1]:=mlen+1;inc(n);t[1]:=1;//前一个程序中仅有的改动

fork:=2tomlen+1dofori:=ndownto1doiff[i]=kthenbeginj:=i-1;while(j>0)and(h[j]<>h[i])dobeginif(h[j]<h[i])and(f[j]+1=k)theninc(t[i],t[j]);dec(j);end;end;writeln(t[n]);end.到目前通过所有数据的程序:t[1]:=1;//前一测试数据712233541223444912346581091234556778122335451223444581212335412123344

81345123512341234但这组数据过不了:82345123512341234测试数据但这组数据过不了:经典赛题1、导弹拦截（注意：第二问不可以用每次删除最长不上升序列的方法做。比如，当来袭的导弹共有4颗，高度依次为2413的时候，如果不巧找到的最长不上升序列为41，那么剩下的2和3就只能另外启用两套系统了。这显然不是最优解。）第二问用贪心法即可。每颗导弹来袭时，使用能拦截这颗导弹的防御系统中上一次拦截导弹高度最低的那一套来拦截。若不存在符合这一条件的系统，则使用一套新系统。

经典赛题1、导弹拦截（注意：第二问不可以用每次删除最长不上升

合唱队形

【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1,T2,…,TK，则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。合唱队形

【问题描述】N位同学站成一排，音乐老师要请其中的输入文件

输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

-输出文件

输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

-样例输入

8

186186150200160130197220

-样例输出

4

输入文件

输入文件chorus.in的第一行是一个整设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：方格取数？（可以用最长不下降模型吗？）对比VIJOS飞翔飞翔:8080/JudgeOnline/showproblem?problem_id=1907设有N*N的方格图(N<=10,我们将其中的某些方格中填入正某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

输入

输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。

输出

只需输出一个整数，表示2条路径上取得的最大的和。后面是另外思路的DP参考解答某人从图的左上角的A点出发，可以向下行走，也可以向右走，直分析:这是一道所谓”路径”类型的DP题.这道题的阶段划分方法有两种:较为简单的一种是按行划分阶段,按列划分状态.如果人只从A点到B点走一次,则可以用DP较方便的解决:从A开始,向下向下递推,依次求出从A点出发到达当前位置(i,j)所能取得的最大的数之和,存放在sum数组中.原始数据存放在data数组中.为处理方便,sum数组加进了0行和0列.状态转移方程为:Sum[i,j]=max{sum[i-1,j],sum[i,j-1]}+data[i,j](1<=i<=n,1<=j<=n)分析:这是一道所谓”路径”类型的DP题.这道题的阶段划分方法如果走两次,能不能够用DP先走一次,求得最大数和,把路径上的数清0,然后再用DP走一次,求得第二最大数和,再把两次的结果相加得到最后的结果呢?这是一种很自然的想法,并且对测试样例也是正确的.但实际这种算法是错误的.例如,对右图数据,若按DP先走一次,将取完红色字体的数,但第二次DP时,两个黑色的数字将无法同时取到.而事实我们可以简单地将第3列和第5列的所有数取完.因此本题所谓走两次其实必须在一次DP时同时考察两条路径.如果走两次,能不能够用DP先走一次,求得最大数和,把路径上考虑两个人同时从A出发,则需要考虑两个人到达任意两个格子(i1,j1)(i2,j2)的情况.即状态要用4个变量来描述:sum[i1,j1,i2,j2]每个人可以从上或左的两个方向达到当前格子,显然前一状态必为:(i1-1,j1),(i2-1,j2)(i1-1,j1),(i2,j2-1)(i1,j1-1),(i2-1,j2)(i1,j1-1),(i2,j2-1)四种情况之一.设p=max{sum[i1-1,j1,i2-1,j2],sum[i1-1,j1,i2,j2-1],sum[i1,j1-1,i2-1,j2],sum[i1,j1-1,i2,j2-1]}则有据此,可写出程序.易知,本算法的时间空间复杂度均为O(n^4)后一段分析是按对角线方向来划分阶段的.这样处理之后,可以把时间复杂性降低一维,把空间复杂性降低到O(n^2),因此该思想方法要认真思考,掌握考虑两个人同时从A出发,则需要考虑两个人到达任意两个格子(i优化方法:1、状态的设计对于本题来说，状态的选定和存储对整个问题的处理起了决定性的作用。我们从（1，1）出发，每走一步作为一个阶段，则可以分成2*n-1个阶段：第一个阶段，两条路径从（1，1）出发；第二个阶段，两条路径可达（2，1）和（1，2）；第三个阶段，两条路径可达的位置集合为（3，1）、（2，2）和（1，3）；

…………

第2*n-1个阶段，两条路径汇聚（n，n）；在第k(1≤k≤2*n-1)个阶段，两条路径的终端坐标（x1，y1）（x2，y2）位于对应的右下对角线上。如下图所示：

阶段1阶段2阶段3阶段4阶段5阶段6阶段7优化方法:1、状态的设计阶段1阶段2阶段3阶段4阶段5阶段如果我们将两条路径走第i步的所有可能位置定义为当前阶段的状态的话，面对的问题就是如何存储状态了。方格取数问题的状态数目十分庞大，每一个位置是两维的，且又是求两条最佳路径，这就要求在存储上必须做一定的优化后才有可能实现算法的程序化。主要的优化就是：舍弃一切不必要的存储量。为此，我们取位置中的x坐标（x1，x2）作状态，其中（1≤x1≤n）and（1≤x2≤n））直接由x坐标计算对应的y坐标：（y1=k+1-x1）and（y1∈{1‥n}）and（y2=k+1-x2）and（y2∈{1‥n}阶段1阶段2阶段3阶段4阶段5阶段6阶段7如果我们将两条路径走第i步的所有可能位置定义为当前阶段的状态2、状态转移方程设两条路径在k阶段的状态为（x1，x2）。由（y1=k+1-x1）∧（y1∈{1..n}）得出第一条路径的坐标为（x1，y1）；由（y2=k+1-x2）∧（y2∈{1..n}）得出第二条路径的坐标为（x2，y2）。假设在k-1阶段，两条路径的状态为（x1’，x2’）且（x1’，x2’）位于（x1，x2）状态的左邻或上邻位置。因此我们设两条路径的延伸方向为d1和d2：di=0，表明第i条路径由（xi’，yi’）向右延伸至（xi，yi）；di=1，表明第i条路径由（xi’，yi’）向下延伸至（xi，yi）（1≤i≤2）。显然（x1’=x2’）∧（d1=d2），表明两条路径重合，同时取走了（x1’，y1’）和（x1，y1）中的数，这种取法当然不可能得到最大数和的。分析两种可能：⑴若x1=x2，则两条路径会合于x1状态，可取走（x1，y1）中的数(如下图)；

x2’(x1’)x1’(x2’)x1=x2

2、状态转移方程⑵若x1≠x2，则在k阶段，第一条路径由x1’状态延伸至x1状态，第二条路径由x2’状态延伸至x2状态，两条路径可分别取走（x1，y1）和（x2，y2）中的数(如下图)；X1’→X1X2’↓X2设

f[k，x1，x2]—在第k阶段，两条路径分别行至x1状态和x2状态的最大数和。显然k=1时，f[1，1，1]=data[1,1]；k≥2时，f[k，x1，x2]=max{f[k-1，x1’，x2’]+data[x1，y1](x1=x2)，f[k-1，x1’，x2’]+data[x1，y1]+data[x2，y2](x1≠x2)}

1≤k≤2*n-1，x1’可达x1的状态集合，x2’可达x2的状态集合，（x1’≠x2’）∨(d1≠d2)；上述状态转移方程符合最优子结构和重叠子问题的特性，因此适用于动态程序设计方法求解。由于第k个阶段的状态转移方程仅与第k-1个阶段的状态发生联系，因此不妨设

f0—第k-1个阶段的状态转移方程；

f1—第k个阶段的状态转移方程；初始时，f0[1，1]=0。经过2*n-1个阶段后得出的f0[n，n]即为问题的解。此为空间优化！⑵若x1≠x2，则在k阶段，第一条路径由x1’状态延伸至x13、多进程决策的动态程序设计由于方格取数问题是对两条路径进行最优化决策的，因此称这类动态程序设计为分阶段、多进程的最优化决策过程。设阶段i：准备走第i步（1≤i≤2*n-1）；状态（x1，x2）：第i步的状态号（1≤x1，x2≤i。x1，x2∈{1..n}）决策（d1，d2）：第一条路径由x1状态出发沿d1方向延伸、第二条路径由x2状态出发沿d2方向延伸，可使得两条路径的数和最大（0≤d1，d2≤1。方向0表示右移，方向1表示下移）；本题的启示:1.如果某个状态变量可以由另一个状态变量计算产生(例如y坐标可由x坐标计算生成),则这个状态变量可以不保存;这样可以压缩状态.2.如果K阶段的状态只与K-1阶段的状态值有关,则可以利用滚动数组,只保留前后两个阶段的状态值.初值状态值保存在F0中,然后由F0去递推计算F1,每次计算完成后,又将F1的值赋值到F0中,以便下一阶段的计算.动态规划总结ppt课件fillchar(f0，sizeof(f0)，0)；{行走前的状态转移方程初始化}f0[1，1]←data[1,1]；fori←2to2*n-1do{阶段：准备走第i步}beginfillchar(f1，sizeof(f1)，0)；{走第i步的状态转移方程初始化}forx1←1toido{枚举两条路径在第i-1步时的状态x1’和x2’}forx2←1toidobegin

计算y1和y2；if(x1，y1)和(x2，y2)在界内thenford1←0to1do{决策：计算两条路径的最佳延伸方向}ford2←0to1dobegin

第1条路径沿d1方向延伸至(x1’，y1’）；第2条路径沿d2方向延伸至(x2’，y2’)；

if(x1’，y1’)和(x2’，y2’)在界内{计算第i步的状态转移方程}thenf1[x1，x2]←max{f0[x1’，x2’]+data[x1，y1]∣x1=x2，f0[x1’，x2’]+data[x1，y1]+data[x2，y2]∣x1≠x2}end；{for}end；{for}f0←f1；{记下第i步的状态转移方程}end；{for}输出两条路径取得的最大数和f0[n，n]fillchar(f0，sizeof(f0)，0)；{行走前constmaxn=20;dir:array[1..2,1..2]ofinteger=((-1,0),(0,-1));vara,f0,f1:array[0..maxn,0..maxn]ofinteger;n,i,j,k,d1,d2:integer;x1,y1,x2,y2,x1p,y1p,x2p,y2p,max:integer;beginreadln(n);readln(i,j,k);whilenot((i=0)and(j=0)and(k=0))dobegina[i,j]:=k;readln(i,j,k);end;f0[1,1]:=a[1,1];fork:=2to2*n-1dobeginfillchar(f1,sizeof(f1),0);forx1:=1tokdobeginy1:=k+1-x1;if(x1<=n)and(1<=y1)and(y1<=n)thenbeginforx2:=1tokdobeginy2:=k+1-x2;

constmaxn=20;if(x2<=n)and(1<=y2)and(y2<=n)thenbeginmax:=0;ford1:=1to2doford2:=1to2dobeginx1p:=x1+dir[d1,1];x2p:=x2+dir[d2,1];iff0[x1p,x2p]>maxthenmax:=f0[x1p,x2p];end;if(x1=x2)and(y1=y2)thenf1[x1,x2]:=max+a[x1,y1]elsef1[x1,x2]:=max+a[x1,y1]+a[x2,y2];end;end;end;end;f0:=f1;end;writeln(f0[n,n]);end.类似题目:VijosP1143三取方格数if(x2<=n)and(1<=y2)and(y2数塔模型如下所示一个数字三角形

738810274445265写一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字和最大每一步可沿直向下或右斜线向下走1<三角形行数<=100三角形中的数字为整数0，1，，，99数塔模型如下所示一个数字三角形分析:设：f[i,j]为从第i行中的第j个数至第n行的最大的数字和；

则:f[n,j]=a[n,j]

(1<=j<=n)

f[i,j]=max{f[i+1,j],f[i+1,j+1]}

+a[i,j](1<=j<=i,1<=i<=n-1)

f[1,1]即为所求。经典例题:花店橱窗布置参见教材P230例8-5OntheWeb:/doj/showproblem.asp?problem_id=1101

分析:【题目描述】

假设你想以最美观的方式布置花店的橱窗。现在你有F束不同品种的花束，同时你也有至少同样数量的花瓶被按顺序摆成一行。这些花瓶的位置固定于架子上，并从1至V顺序编号，V是花瓶的数目，从左至右排列，则最左边的是花瓶1，最右边的是花瓶V。花束可以移动，并且每束花用1至F间的整数唯一标识。标识花束的整数决定了花束在花瓶中的顺序，如果I＜J，则令花束I必须放在花束J左边的花瓶中。

例如，假设一束杜鹃花的标识数为1，一束秋海棠的标识数为2，一束康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，如下表所示。【题目描述】

花瓶

123451(杜鹃花)723-5-24162(秋海棠)521-410233(康乃馨)-215-4-2020例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得十分难看。

为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果有不止一种的摆放方式具有最大的美学值，则其中任何一直摆放方式都可以接受，但你只要输出任意一种摆放方式。（2）假设条件

1≤F≤100，其中F为花束的数量，花束编号从1至F。

F≤V≤100，其中V是花瓶的数量。

-50≤Aij≤50，其中Aij是花束i在花瓶j中的美学值。

（3）输入第一行包含两个数：F，V。随后的F行中，每行包含V个整数，Aij即为输入文件中第（i+1）行中的第j个数。（4）输出一行，表示程序所产生摆放方式的美学值。样例输入：35723-5-2416521-41023-215-4-2020样例输出：53

（3）输入分析:将问题进行转化，找出问题的原型。将摆放方案的要求用表格表现出来，则摆放方案需要满足：（1）每行选且只选一个数（花瓶），（2）摆放方案的相邻两行中，下面一行的花瓶编号要大于上面一行的花瓶编号。这样可将问题转化成：给定一个数字表格，求解从顶行至底行的一条路径，使得这条路径所经过的数字总和最大，要求满足两个条件：（1）每行选且仅选一个数字；（2）路径中相邻两行数字，必须保证下一行数字的列数大于上一行数字的列数。对比数塔原型，写出动态规划转移方程。设b[i,j]表示美学值表格中第i行的第j个数字，用q[i,j]表示从表格最底层到b[i,j]这个数字的最佳路径的数字和，F表示花束总数，V表示花瓶总数，则有：边界：q[i,V+1]:=-∞(1<=i<=F)q[F,j]:=b[F,j](1<=j<=V)状态转移方程：q[i,j]:=max{q[i+1,k]}(j+1<=k<=V+1)+b[i,j](1<=i<=F-1,1<=j<=V)这样，得出的max{q[1,j]}(1<=j<=V)就是最大的美学值。算法复杂性为：O（FV2）分析:将问题进行转化，找出问题的原型。将摆放方案的要求用表优化看一下这样两个状态的求解方法：q[i,j]=max{q[i+1,k]}(j+1<=k<=V+1)+b[i,j]q[i,j+1]=max{q[i+1,k]}(j+2<=k<=V+1)+b[i,j+1]上面两个状态中求max{q[i+1,k]}的过程中进行了大量重复的比较，非常费时。对状态的表示作修改，用数组t[i,j]表示第i行从第j列起到V列的美学值的最大值，即：t[i,j]=max{q[i,k](j<=k<=V)}(1<=i<=F,1<=j<=V)表示新的状态。经过修改后，因为q[i,j]=t[i+1,j+1]+b[i,j],而t[i,j]=max{t[i,j+1],q[i,j]}(1<=i<=F,1<=j<=V)所以得出新的状态转移方程：t[F,j]=max{t[F,j+1],b[F,j]}(1<=j<=V)t[i,j]=max{t[i,j+1],t[i+1,j+1]+b[i,j]}(1<=j<=V,1<=i<=F-1)这样，得出的最大美学值为t[1,1]，新算法的时间复杂度为O(FV)优化看一下这样两个状态的求解方法：最小代价子母树模型有n堆石子排成一条直线，每堆石子有一定的重量。现在要合并这些石子成为一堆石子，但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力，该体力为所合并的两堆石子的重量之和。问最少需要多少体力才能将n堆石子合并成一堆石子？数据规模:n<=3000样例输入:852476139样例输出:105最小代价子母树模型有n堆石子排成一条直线，每堆石子有一定的重分析令m[i,j]表示归并第i个数到第j数的最小代价,w[i,j]表示第i个数到第j个数的和，这个可以事先计算出来。w[i,j]可以在O(1)的时间内算出.有如下的状态转移方程:阶段：以归并石子的长度为阶段，一共有n-1个阶段。状态：每个阶段有多少堆石子要归并，当归并长度为2时，有n-1个状态；当归并长度为3时，有n-2个状态；当归并长度为n时，有1个状态。决策：当归并长度为2时，有1个决策；当归并长度为3时，有2个决策；当归并长度为n时，有n-1个决策。

forlen:=2tondofori:=1ton-len+1dobeginj:=i+len-1;f[i,j]:=MAXINT;fork:=i+1tojdobegin

参考上面状态转移方程求解分析令m[i,j]表示归并第i个数到第j数的最小代价,w[i优化不难发现这个算法的复杂度是n^3。n的范围是3000，需要优化算法。对于动态规划的优化和搜索的优化是一样的道理。搜索中，如果某状态下不会有最优解，那么就不用继续搜索下去了。动态规划也可以这样来优化。具体方法是：在计算每个状态的值的时候，记录下它所选取的分界点k，用s[i,j]表示当m[i,j]取最优值的时候，选取的k值。那么原状态转移方程中的k的枚举范围便可以从原来的(i+1~j)变为(s[i,j-1]~s[i+1,j])w[i,j]的优化方法:令t[i]表示a[1]到a[i]的和,t[i]可以在输入数据时用O(n)的时间算出然后w[i,j]=t[j]-t[i-1]优化不难发现这个算法的复杂度是n^3。n的范围是3000，需四边形不等式与决策单调性(证明略)凸性：当函数w[i,j]满足：w[i,j]+w[i‘，j’]<=w[i‘,j]+w[i,j’](i<=i‘<j<=j’)时，称w满足四边形不等式。单调性：当函数w[i,j]满足：w[i’,j]<=w[i,j’](i<=i‘<j<=j’)时,称w满足关于区间包含的单调性。这样，对于状态转移方程式：m[i,j]=min{m[i,k-1]+m[k,j]+w[i,j]}(i<k<=j)

如果w[i,j]满足四边形不等式和区间包含单调性，那么m[i,j]也满足四边形不等式。用s[i,j]表示m[i,j]的决策，如果函数m[i,j]满足四边形不等式，则函数s[i,j]满足单调性，即决策单调性：s[i,j]<=s[i,j+]<=s[i+1,j+1]。

则函数s[i,j]的值应该在一个区间内，即：

s[i,j-1]<=s[i,j]<=s[i+1,j]四边形不等式与决策单调性(证明略)由于s[i,j-1]和s[i+1,j]已经在阶段j-i求出，所以在枚举决策变量k时，就可以从s[i,j-1]到s[i+1,j]。于是，我们利用s[i,j]的单调性，得到优化的状态转移方程为：

m[i,j]=0i=ji<j利用这样的决策单调性，就可以把时间复杂性优化到O(n^2)。边界：s[i,i]=is[i,j]的值在m[i,j]取得最优值时，保存、更新例如，对石子归并这道题，先验证w[i,j]满足区间单调性和四边形不等式。对数据ii’jj’237465单调性：w[i’,j]=3+7+4=14w[i,j’]=2+3+7+4+6+5=27故w[i’,j]<=w[i,j’]满足单调性由于s[i,j-1]和s[i+1,j]已经在阶段j-i求出，四边形不等式：w[i,j]+w[i’,j’]=(2+3+7+4)+(3+7+6+5)=16+21=37w[i’,j]+w[i,j’]=(3+7+4)+(2+3+7+4+6+5)=14+27=41故w[i,j]+w[i’,j’]<=w[i’,j]+w[i,j’]故石子合并可利用四边形不等式进行优化。上述方法是具有普遍性的。对于状态转移方程与①式类似，且w[i,j]满足四边形不等式的动态规划问题，都可以采用相同的优化方法，如最优二叉排序树（NOI`96）等。四边形不等式：用四边形不等式优化的经典题目石子合并--在一圆形操场四周摆放N堆石子(N≤2000),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(≤20), (1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大输入数据:

第一行为石子堆数N;

第二行为每堆石子数,每两个数之间用一空格分隔.输出数据:

从第1至第N行为得分最小的合并方案.第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.用四边形不等式优化的经典题目石子合并--在一圆形操场四周摆放分析：用data[i,j]表示将从第i颗石子开始的接下来j颗石子合并所得的分值，mx[i,j]表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：mx[i,j]=max(mx[i,k]+mx[i+k,j–k]+data[i,k]+data[i+k,j–k])(2<=k<=j)mx[i,1]=0同样的，我们用mn[i,j]表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：mn[i,j]=min(mn[i,k]+mn[i+k,j–k]+data[i,k]+data[i+k,j–k])(0<=k<=j)mn[i,0]=0这样，我们完美地解决了这道题。时间复杂度也是O(n2)。分析：2：邮局(IOI`2000)[问题描述]按照递增顺序给出一条直线上坐标互不相同的n个村庄，要求从中选择p个村庄建立邮局，每个村庄使用离它最近的那个邮局，使得所有村庄到各自所使用的邮局的距离总和最小。试编程计算最小距离和，以及邮局建立方案。样例输入：1052367911224450样例输出：927224450参见教材P2342：邮局(IOI`2000)[问题描述]分析：将n个村庄按坐标递增依次编号为1，2，……，n，各个邮局的坐标为d[1..n]，状态表示描述为：m[i,j]表示在前j个村庄建立i个邮局的最小距离和。所以，m[p,n]即为问题的解，且状态转移方程和边界条件为：m[1,j]=w[1,j]i≤j其中w[i,j]表示在d[i..j]之间建立一个邮局的最小距离和，可以证明，当仅建立一个邮局时，最优解出现在中位数，即设建立邮局的村庄为k，则，于是，我们有：

，分析：，同时，令s[i,j]=k，记录使用前i-1个邮局的村庄数，便于在算出最小距离和之后构造最优建立方案。上述算法中w[i,j]可通过O(n)时间的预处理（怎么预处理？），在O(1)的时间内算出，所以，该算法的状态总数为O(n*p)，每个状态转移的状态数为O(n)，每次状态转移的时间为O(1)，该算法总的时间复杂度为O(p*n2)。[算法优化-本优化算法来自毛子青]本题的状态转移方程与石子归并的状态转移方程十分相似，因此我们猜想其决策是否也满足单调性，即：s[i-1,j]≤s[i,j]≤s[i,j+1]首先，我们来验证函数w满足四边形不等式，即：

用样例输入数据可以进行验证。验证完成后，还应该证明m[i,j]满足四边形不等式和s[i,j]满足单调性。这几步完成后，就可以利用决策单调性进行优化了。

同时，令s[i,j]=k，记录使用前i-1个邮局的村庄数，便优化后的状态转移方程为：m[1,j]=w[1,j]

s[i,j]=k同上文所述，优化后的算法时间复杂度为O(n*p)。请在完成邮局的基础上，认真研究习题教材P748.4书的复制四边形不等式优化的实质是对结果的充分利用。它通过分析状态值之间的特殊关系，推出了最优决策的单调性，从而在计算当前状态时，利用已经计算过的状态所做出的最优决策，减少了当前的决策量。这就启发我们，在应用动态规划解题时，不仅可以实现状态值的充分利用，也可以实现最优决策的充分利用。这实际上是从另一个角度实现了“减少冗余”。优化后的状态转移方程为：s[i,j]=k3、能量项链

vijos1312

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

3、能量项链vijos1312在Mars星球上，每个

例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(4⊕1)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。【输入文件】输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i<N时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。【输出文件】输出文件energy.out只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3背包模型0/1背包有限次背包无限背包部分背包背包模型0/1背包0/1背包在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即Maxp=max{p1*x1+p2*x2+...+pi*xi}(其1<=i<=n，x取0或1，取1表示选取物品i),且满足w1*x1+w2*x2+…+wi*xi<=c。令f[i,j]表示前i个物品,容量为j时取得的最大价值,则针对第i件物品进行决策:0表示不放入背包,此时最大价值为f[i-1,j]1表示放入背包,此时最大值为f[i-1,j-wi]+pi因此有状态转移方程:F[i,j]:=max{f[i-1,j],f[i-1,j-w[i]]+p[i](j>=w[i])}(0<=i<=n,1<=j<=c)边界:f[0,j]=0(0<=j<=c)时间复杂性:O(N^2)

0/1背包在0/1背包问题中，需对容量为c的背包进行装经典例题:花店橱窗布置把该题看成背包模型,则有:令m[k,s]表示前k个花瓶放前s束花的最大美学值,针对第k个花瓶是否放花进行决策:0表示不放,则最大美学值为f[k-1,s]1表示要放,则最大美学值为f[k-1,s-1]+a[s,k]状态转移方程为:m[k,s]=max{f[k-1,s],f[k-1,s-1]+a[s,k]}(2<=k<=V,1<=s<=F)边界:m[k,0]=0(1<=k<=V)m[1,1]=a[1,1]m[i,j]=-∞(i<j)经典例题:花店橱窗布置把该题看成背包模型,则有:constmaxn=200;mini=-20000;vara,m:array[0..maxn,0..maxn]ofinteger;F,v:integer;i,j,k,s:integer;beginassign(input,'flower10.inp');reset(input);readln(F,v);fori:=1toFdoforj:=1toVdoread(a[i,j]);m[1,1]:=a[1,1];fori:=1toVdoforj:=i+1toFdom[i,j]:=mini;fori:=1toVdom[i,0]:=0;

fork:=2toVdofors:=1tokdobeginm[k,s]:=m[k-1,s];j:=m[k-1,s-1]+a[s,k];ifm[k,s]<jthenm[k,s]:=j;end;writeln(m[V,F]);end.constmaxn=200;fork:=2toV优化由于当前阶段k的状态只与前一阶段k-1的状态值有关，可用两个一维数组进行滚动赋值。优化由于当前阶段k的状态只与前一阶段k-1的状态值有关，可用有限次背包金明的预算方案

VijosP1313金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：有限次背包金明的预算方案VijosP1313如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件budget.in的第1行，为两个正整数，用一个空格隔开：

Nm（其中N（<32000）表示总钱数，m（<60）为希望购买物品的个数）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数

vpq（其中v表示该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）【输出文件】输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件题目大意

给出购买总费用M和N件物品，每件物品的特性有：价格、重要度、以及是主件还是附件。对于每个附件，必须购买主件，才能购买该附件。求在购买总费用内，能购买多少物品，使得所有物品的价格*重要度的总和最大。题目大意

给出购买总费用M和N件物品，每件物品的特性本题与经典动态规划——01背包问题十分类似。但不同点是，多出了主、附件之分。对于每个附件，必须先购买主件。注意到每个主件最多只有2个附件和附件不再带有附件，所以考虑把附件和主件捆绑在一起处理。对于一个没有附件的主件，直接做背包问题的动态规划。对于有附件的主件（最多只有2个直属的附件），枚举所有的捆绑可能，即单独一个主件；一个主件+两个附件之一；或一个主件+两个附件，一共最多4种可能。每一种组合方式为1个背包，分别使用动态规划解背包问题。本题与经典动态规划——01背包问题十分类似。但不同点是，多出无限次背包USACO1.2ScoreInflation进行一次竞赛，总时间M固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti（解答此题所需的时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在M以内的前提下，所得的总分最大，求最大的得分。输入:第一行MN表示总的时间和题目数量(1<=M<=10000,1<=N<=1000)第二行N个数,表示解每个题的时间,用空格分隔第三行N个数,表示解每个题的分数,用空格分隔输出:一个数,最大的得分样例输入:20432454145样例输出:25无限次背包USACO1.2ScoreInflation分析:设f[i,j]表示选择前i种题目,总时间为j时的最大分数,经分析可得出这样的状态转移方程:f[i,j]=max[f[i-1,j-k*t[i]]+k*s[i](0<=k<=jdivt[i])}(1<=i<=nt[i]<=j<=m)分析:设f[i,j]表示选择前i种题目,总时间为j时的最大分求恰好装满背包的情况数USACO货币体系(MoneySystems)母牛们不但创建了他们自己的政府而且建立了自己的货币体系。他们对货币的币值感到好奇。例如,一种货币体系是由1,5,10,20,25,50和100的单位币值组成的。母牛想知道对于一个确定的金额,如果用货币体系中的货币来构造,一共有多少种不同的方法。举例来说,使用货币体系{1,2,5,10,...}产生18单位金额的一些可能的方法是:18*1,9*2,8*2+2*1,3*5+2+1,等等。请写一个程序来计算有多少种方法用给定的货币体系来构造给定数值的金额。保证总的方法数小于Int64求恰好装满背包的情况数USACO货币体系(MoneyS输入格式:货币体系中货币的种类V。(1<=V<=25)要构造的金额N。(1<=N<=10,000)第1行:二个整数，V和N第2..V+1行：货币体系的V个整数(每行一个每行没有其它的数)。样例输入:310125输出格式:单独的一行,即总的构造的方案数。样例输出:10输入格式:分析给定一组硬币的面值和一个n，要求输出一共有多少种组合方法可以组合出价值n。用一个长度为n＋1的数组记录组合方法的种数，对于每一个面值为v的硬币，用f[i]=f[i]+f[i-v],i>=v更新数组,（初始f[0]=1)，最后array[n]就是所求的结果。即对于每一个硬币，凡是不小于它的面值的总和的构造数目都会增