取数模型与DP

取数模型与DP1、数字三角形每行取一个（下面的位置是上面的邻居），从上往下，求最大和。样例：输入N=5，下面是5行数字：738810274445265DP方程：a[i,j]:=max{a[i+1,j],a[i+1,j+1]}+a[i,j](1=i,j=n-1)主要程序段：fori:=n-1downto1do//从倒数第二行往上做。Forj:=1toidoIfa[i+1,j]a[i+1,j+1]thena[i,j]:=a[i,j]+a[i+1,j]Elsea[i,j]:=a[i,j]+a[i+1,j+1];Writeln(a[1,1]);2、求环形整数串的最大连续和。P1308输入样例6-2301-4880输出样例82线形DP：转化成环形分两种情况：1、如：-2201-481，显然其最大和连续子串是201，其和是3。选的是中间的一段，这种情况直接使用上述的线形DP公式。2、样例：-2301-4880结果82选的是断开处的两端，要当成环处理。怎样处理第2种情况呢？第2种情况可以找中间连续一段最小的值，然后拿所有数的和--最小值DP方法：在上页DP方程的基础上，Ans=MAX(线性DP最大值,sum-线性DP最小值);N值很大，如果超过数组能定义的范围，可以不用数组保存这N个数，而是直接读一个数就处理一次。3、求最长不下降序列P1194样例：[输入]14{表示14个数}13791638243718441921226315[输出]8{长度为8}79161819212263{其中一种取法}从前往后，每选一个数，总可以得到此时的最长序列，这一段的最长序列不会因为后面的不同取数方法而改变，故无后效性。DP方程为：F[i]=MAX(F[1],………,F[i-1]，其中所项的一项必须能与F[i]相连接)+1。4、求两串字符的最长公共子序列[输入样例]ABCBDABBDCABA[输出样例]4BCBA样例：C[4，5]因为x[4]=y[5],所以c[4,5]=c[3,4]+1C[5,4]因为x[5]y[4],所以c[5,4]=max{c[5,3],c[4,4]}最后输出C[7，6]的值。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。C[i,j]的值表示：取X列的前i个字母，取y列的前j个字母得到的公共最长子序列的长度。边界：当i=0或j=0时，c[i,j]=0。fori:=1tolength(x)doforj:=1tolength(y)doifx[i]=y[j]thenc[i,j]:=c[i-1,j-1]+1elseifc[i-1,j]c[i,j-1]thenc[i,j]:=c[i-1,j]elsec[i,j]:=c[i,j-1]；5、求三串中的最长公共子串。P1338胖男孩varsol:array[0..100,0..100,0..100]ofstring[100];sa,sb,sc:string[1la,lb,lc:integer;procedurework;vari,j,k:integer;max:string;beginfori:=1toladoforj:=1tolbdofork:=1tolcdobeginmax:='';sol[i,j,k]:='';iflength(sol[i-1,j,k])length(max)thenmax:=sol[i-1,j,k];iflength(sol[i,j-1,k])length(max)thenmax:=sol[i,j-1,k];iflength(sol[i,j,k-1])length(max)thenmax:=sol[i,j,k-1];iflength(sol[i-1,j-1,k])length(max)thenmax:=sol[i-1,j-1,k];iflength(sol[i-1,j,k-1])length(max)thenmax:=sol[i-1,j,k-1];iflength(sol[i,j-1,k-1])length(max)thenmax:=sol[i,j-1,k-1];if(sa[i]=sb[j])and(sb[j]=sc[k])and((length(sol[i-1,j-1,k-1]+sa[i]))length(max))thenmax:=sol[i-1,j-1,k-1]+sa[i];sol[i,j,k]:=max;end;end;beginreadln(sa);readln(sb);readln(sc);la:=length(sa);lb:=length(sb);lc:=length(sc);work;writeln(length(sol[la,lb,lc]));end.6、机器分配P1029M个数N个人取，取不同的数得到的代价不同，怎样取，代价最大。32//3个数，2个人取123//第一个人取123个数的代价234//第二个人取123个数的代价输出：4方案一：第一个人取2个数，代价2，第二个人取1个数，代价2，总和是4方案二：第一个人取3个数，代价3方案三：第一个人取1个数，代价1，第二个人取2个数，总和是4。。。。虽然方案很多，但最大代价和是4固定的。用A[i,j]保存下面的N行数据。F[i,j]表示第i个人取j台的最大价值。能否用前面的状态来表示呢？如F[2，3]表示2个公司分配3台的最大价值。可以用什么来表示？F[1,0]+A[2,3]F[1,1]+A[2,2]F[2，3]=maxF[1,2]+A[2,1]F[1,3]+A[2,0]DP方程：F[i，j]=max{F[i-1,k]+A[i,j-k]}(k取0..m)边界：F[1,i]=A[1,i](i取1..n)7、P1159乘法游戏将N个数中的2-N个数排一个顺序，每次取一个，将它与相邻两数相乘，求乘积和最大。样例说明：61015050205取数顺序4123从而得到：50*1*50+50*1*20+20*1*5+1*10*5=3650用F[i,j]表示从a[i]到a[j]得到的最小值。先算出最小的几个，每组选3个数。F[1,3]=F[2,4]=F[3,5]F[4,6]开始扩大范围，每组选4个数。看能不能用前面的方法进行规划。F[1,4]=F[2,5]=F[3,6]=8、最小代价子母树：将N个数中相邻的两数合并后，变成一个数，再放到原位置，直到最后变成一个数，共进行N-1次合并，求这N-1次过程中，将每次得到的一个数的相加，求最小的和。用F[I,j]表示从i到j的最小代价。A、B方案是F[1，3]+10C方案是F[1，2]+F[3，4]+10D、E方案是F[2，4]+10推导出动态方程为：F[1,4]=min{f[1,3],f[1,2]+f[3,4],f[2,4]}+10其中f[1,3]=min{f[1,2],f[2,3]}+7=10F[2,4]=min{f[2,3],f[3,4]}+6=9当n=6时：F[1,6]=min{f[1,5],f[1,2]+f[3,6],f[1,3]+f[4,6],f[1,4]+f[5,6],f[2,6]}+g(1,6)//g数组用来存放和其中：f[3,6]=min{f[3,5],f[3,4]+f[4,5],f[4,6]}+g(3,6)对于一般情况有：F[1,n]=min{f[1,n-1],f[1,2]+f[3,n],……,f[1,n-2]+f[n-1,n],f[2,n]}+g(1,n)f[i,j]=min{f[i,j-1],f[i,j+1]+f[i+2,j],f[i,i+2]+f[i+3,n],……,f[i+1,j]}+g(m,n)变形：P1015能量项链将链转换成列：将1234复制一下，如4个数是：4325，复制一下，变成43254325下面只要求出max{F[1,4],F[2,5]……F[4,7]}9、最大乘积P1192题意：在N个数字中插入K个乘号，求最大乘积。样例输入：421231输出：62算法：采用背包算法，穷举乘号的位置。实际上这道题的命题者想到的算法是DP，请你写出DP方程。用F[n,k]表示在N个数中插入K个乘号的最大值先计算F[i,1]i从2取到n,下面请写出F[n,k]=?F[n,k]=max{F[n-1,k-1]*A(n,n),F[n-2,k-1]*A(n-1,n)……..F[k,k-1]*A(k+1,n)其中A(I,j)表示N串中从第i个字符取到第j个字符的整数。vari1,n,i,j,k:longint;max,s:qword;st:string;g:array[1..20]ofinteger;a:array[1..20,1..20]ofqword;f:array[0..10,0..10]ofqword;beginreadln(n,k);readln(st);fori:=1tondo//分解出i到j的数forj:=1tondoval(copy(st,i,j-i+1),a[i,j]);fori:=2tondo//求1个乘号的最大值beginmax:=0;forj:=1toi-1doifa[1,j]*a[j+1,i]maxthenmax:=a[1,j]*a[j+1,i];f[i,1]:=max;end;fori:=2tokdo//DP求K个乘号forj:=i+1ton-k+idobeginmax:=0;fori1:=j-1downtoidoiff[i1,i-1]*a[i1+1,j]maxthenmax:=f[i1,i-1]*a[i1+1,j];f[j,i]:=maxend;writeln(f[n,k])end.10、花店橱窗布置P1420输入：35723–5–2416521-41023-215-4-2020输出：53说明：取的是245也就是：从5个里面怎样选3个，得到最大值。每行选一个，下一个数在上一个数的后面列。用F[i,j]表示在前i列中j行中选，每行选1个数，且列不断增加，共j个数，得到的最大值。上例中最后要求的是F[5，3]=F[4,2]+a[3,5]F[3,2]+max{A[3,4]—A[3,5]}maxF[2,2]+max{A[3,3]—A[3,5]}以上是两次DP。从而得到DP方程：F[i-1,j-1]+a[j,i]F[I,j]=maxF[i-2,j-1]+max{a[j,i-1]---a[j,i]}…..F[j-1,j-1]+max{a[j,j]----a[j,i]}vari2,i1,n,i,j,k,max,max1:longint;a:array[1..100,1..100]oflongint;f:array[0..100,0..100]oflongint;beginreadln(k,n);fori:=1tokdobeginforj:=1tondoread(a[i,j]);readln;end;f[1,1]:=a[1,1];fori:=2tondoforj:=1toidobeginmax:=-maxlongint;fori1:=j-1toi-1dobeginmax1:=-maxlongint;fori2:=i1+1toidoifa[j,i2]max1thenmax1:=a[j,i2];ifmax1+f[i1,j-1]maxthenmax:=max1+f[i1,j-1];end;f[i,j]:=max;end;writeln(f[n,k])end.11、构建双塔P1466从N个数选部分数，分成两组，要求两组的和相同，求最大的和，无法输出：“Impossible”1≤N≤100样例：输入：513452输出：7样例：13452和为15，当然如果要分两组，如果高度差为1，此时分组为：7、8；则F[5，1]＝8，如果两组的差为0，即F[5，0]则是所要求的最终解。F[i,j]=X表示前i个数，高度差是j，这时的最大值是X因此，F[5，1]＝8，表示取前5个数分两组时，当两组差是1的时候，这时得到的最大值是8。现在往前DP，根据4个数来求第5个数。（1）、第i件物品不选，F[i-1,j](2)、第i件物品选