资源描述：
《取数模型与DP》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、取数模型与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,
2、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值很大，如果超过数组能定义的范围，可以不用数
3、组保存这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、[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[
5、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]:
6、='';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)th
7、enmax:=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)
8、;lb:=length(sb);lc:=length(sc);work;writeln(length(sol[la,lb,lc]));end.6、机器分配P1029M个数N个人取，取不同的数得到的代价不同，怎样取，代价最
