取数模型与DP.doc

取数模型与DP1、数字三角形 每行取一个（下面的位置是上面的邻居），从上往下，求最大和。样例：输入N=5，下面是5行数字：73 88 1 02 7 4 4 4 5 2 6 5 DP方程：ai,j:=maxai+1,j, ai+1,j+1+ai,j (1=i,jai+1,j+1 then ai,j:=ai,j+ ai+1,j Else ai,j:=ai,j+ ai+1,j+1; Writeln(a1,1);2、求环形整数串的最大连续和。P1308输入样例6-2 3 0 1 -48 80输出样例82线形DP：转化成环形分两种情况：1、 如：-2 2 0 1 -48 1，显然其最大和连续子串是2 0 1，其和是3。 选的是中间的一段，这种情况直接使用上述的线形DP公式。2、样例： -2 3 0 1 -48 80 结果 82 选的是断开处的两端，要当成环处理。怎样处理第2种情况呢？第2种情况可以找中间连续一段最小的值，然后 拿所有数的和-最小值DP方法：在上页DP方程的基础上，Ans=MAX(线性DP最大值, sum-线性DP最小值);N值很大，如果超过数组能定义的范围，可以不用数组保存这N个数，而是直接读一个数就处理一次。3、求最长不下降序列 P1194样例：输入 14 表示14个数 13 7 9 16 38 24 37 18 44 19 21 22 63 15 输出 8 长度为8 7 9 16 18 19 21 22 63 其中一种取法从前往后，每选一个数，总可以得到此时的最长序列，这一段的最长序列不会因为后面的不同取数方法而改变，故无后效性。 DP方程为：Fi=MAX(F1,Fi-1，其中所项的一项必须能与Fi相连接)+1。4、求两串字符的最长公共子序列 输入样例 ABCBDABBDCABA输出样例 4BCBA样例：C4，5 因为x4= y5,所以 c4,5=c3,4+1 C5,4 因为 x5 y4,所以 c5,4=maxc5,3, c4,4 最后输出 C7，6的值。用ci,j记录序列Xi和Yj的最长公共子序列的长度。Ci,j的值表示：取X列的前i个字母，取y列的前j个字母得到的公共最长子序列的长度。边界：当i=0或j=0时，ci,j=0。 for i:=1 to length(x) do for j:=1 to length(y) do if xi=yj then ci,j:=ci-1,j-1+1 else if ci-1,jci,j-1 then ci,j:=ci-1,j else ci,j:=ci,j-1；5、求三串中的最长公共子串。 P1338 胖男孩var sol:array0.100,0.100,0.100of string100;sa,sb,sc:string1la,lb,lc:integer;procedure work;var i,j,k:integer; max:string;begin for i:=1 to la do for j:=1 to lb do for k:=1 to lc do begin max:=; soli,j,k:=; if length(soli-1,j,k)length(max) then max:=soli-1,j,k; if length(soli,j-1,k)length(max) then max:=soli,j-1,k; if length(soli,j,k-1)length(max) then max:=soli,j,k-1; if length(soli-1,j-1,k)length(max) then max:=soli-1,j-1,k; if length(soli-1,j,k-1)length(max) then max:=soli-1,j,k-1; if length(soli,j-1,k-1)length(max) then max:=soli,j-1,k-1; if (sai=sbj)and(sbj=sck)and ( length(soli-1,j-1,k-1+sai) ) length(max)then max:=soli-1,j-1,k-1+sai; soli,j,k:=max; end;end;beginreadln(sa); readln(sb); readln(sc); la:=length(sa); lb:=length(sb); lc:=length(sc); work;writeln(length(solla,lb,lc);end.6、机器分配P1029M个数N个人取，取不同的数得到的代价不同，怎样取，代价最大。3 2 / 3个数，2个人取1 2 3 /第一个人取1 2 3个数的代价2 3 4 /第二个人取1 2 3个数的代价输出：4方案一：第一个人取2个数，代价2，第二个人取1个数，代价2，总和是4方案二：第一个人取3个数，代价3方案三：第一个人取1个数，代价1，第二个人取2个数，总和是4。虽然方案很多，但最大代价和是4固定的。用Ai,j保存下面的N行数据。Fi,j表示第i个人取j台的最大价值。能否用前面的状态来表示呢？如F2，3表示2个公司分配3台的最大价值。可以用什么来表示？ F1,0+A2,3 F1,1+A2,2F2，3=max F1,2+A2,1 F1,3+A2,0DP方程： Fi，j=maxFi-1,k+Ai,j-k (k取0.m) 边界：F1,i=A1,i (i取1.n)7、P1159 乘法游戏将N个数中的2-N个数排一个顺序，每次取一个，将它与相邻两数相乘，求乘积和最大。样例说明： 6 10 1 50 50 20 5取数顺序 4 1 2 3从而得到：50*1*50+50*1*20+20*1*5+1*10*5=3650用Fi,j表示从ai到aj得到的最小值。先算出最小的几个，每组选3个数。F1,3= F2,4= F3,5 F4,6开始扩大范围，每组选4个数。看能不能用前面的方法进行规划。F1,4= F2,5= F3,6= 8、最小代价子母树：将N个数中相邻的两数合并后，变成一个数，再放到原位置，直到最后变成一个数，共进行N-1次合并，求这N-1次过程中，将每次得到的一个数的相加，求最小的和。用FI,j表示从i到j的最小代价。 A、B方案是F1，3+10C方案是 F1，2+F3，4+10D、E方案是 F2，4+10推导出动态方程为：F1,4= minf1,3, f1,2+f3,4, f2,4 +10 其中 f1,3=minf1,2, f2,3+7 = 10 F2,4=minf2,3, f3,4+6 = 9当n=6时：F1,6=minf1,5, f1,2+f3,6, f1,3+f4,6, f1,4+f5,6,f2,6 +g(1,6) /g数组用来存放和 其中：f3,6=minf3,5, f3,4+f4,5, f4,6+g(3,6)对于一般情况有：F1,n=minf1,n-1,f1,2+f3,n,f1,n-2+fn-1,n,f2,n+g(1,n)fi,j=minfi,j-1,fi,j+1+fi+2,j,fi,i+2+fi+3,n,fi+1,j+g(m,n)o 变形：P1015 能量项链 将链转换成列：将1 2 3 4 复制一下，如4个数是：4 3 2 5，复制一下，变成 4 3 2 5 4 3 2 5下面只要求出maxF1,4,F2,5 F4,79、最大乘积 P1192 题意：在N个数字中插入K个乘号，求最大乘积。样例输入：4 21231输出：62算法：采用背包算法，穷举乘号的位置。实际上这道题的命题者想到的算法是DP，请你写出DP方程。用Fn,k表示在N个数中插入K个乘号的最大值先计算Fi,1 i从2取到n, 下面请写出Fn,k=?Fn,k=max Fn-1,k-1*A(n,n), Fn-2,k-1*A(n-1,n). Fk,k-1*A(k+1,n)其中 A(I,j)表示N串中从第i个字符取到第j个字符的整数。var i1,n,i,j,k:longint; max, s:qword; st:string; g:array1.20 of integer; a:array1.20,1.20 of qword;f:array0.10,0.10 of qword; begin readln(n,k); readln(st); for i:=1 to n do /分解出i到j的数 for j:=1 to n do val(copy(st,i,j-i+1),ai,j); for i:=2 to n do /求1个乘号的最大值 begin max:=0; for j:=1 to i-1 do if a1,j*aj+1,imax then max:=a1,j*aj+1,i; fi,1:=max; end;for i:=2 to k do /DP 求K个乘号 for j:=i+1 to n-k+i do begin max:=0; for i1:=j-1 downto i do if fi1,i-1*ai1+1,jmax then max:=fi1,i-1*ai1+1,j; fj,i:=max end; writeln(fn,k) end.10、花店橱窗布置P1420输入：3 5 7 23 5 24 165 21 -4 10 23-21 5 -4 -20 20输出：53说明：取的是2 4 5也就是：从5个里面怎样选3个，得到最大值。每行选一个，下一个数在上一个数的后面列。用Fi,j 表示在前i列中j行中选，每行选1个数，且列不断增加，共j个数，得到的最大值。上例中最后要求的是F5，3= F4,2+a3,5 F3,2+maxA3,4A3,5 max F2,2+maxA3,3A3,5以上是两次DP。从而得到DP方程： Fi-1,j-1+aj,iFI,j=max Fi-2,j-1+maxaj,i-1-aj,i . Fj-1,j-1+maxaj,j-aj,ivar i2,i1,n,i,j,k,max,max1:longint; a:array1.100,1.100 of longint; f:array0.100,0.100 of longint; begin readln(k,n); for i:=1 to k do begin for j:=1 to n do read(ai,j); readln; end; f1,1:=a1,1; for i:=2 to n do for j:=1 to i do begin max:=-maxlongint; for i1:=j-1 to i-1 do begin max1:=-maxlongint; for i2:=i1+1 to i do if aj,i2max1 then max1:=aj,i2; if max1+fi1,j-1max then max:=max1+fi1,j-1; end; fi,j:=max; end; writeln(fn,k) end.11、构建双塔 P1466 从N个数选部分数，分成两组，要求两组的和相同，求最大的和，无法输出：“Impossible ” 1N100 样例：输入：51 3 4 5 2输出：7样例：1 3 4 5 2 和为15，当然如果要分两组，如果高度差为1，此时分组为：7、8；则F5，18，如果两组的差为0，即F5，0则是所要求的最终解。Fi,j=X 表示前i个数，高度差是j，这时的最大值是X因此，F5，18，表示取前5个数分两组时，当两组差是1的时候，这时得到的最大值是8。现在往前DP，根据4个数来求第5个数。（1）、第i件物品不选，Fi-1,j(2)、第i件物品选，放到了较矮的那个塔上，而且矮塔仍然为矮塔，填补了高度差(3)、第i件物品选，放到了较矮的那个塔上，但矮塔变成了高塔但有条件限制：hij(4)、第i件物品选，放到了较高的那个塔上，增加了高度差因此，可以用Fi-1,j-hi +hi条件限制：J=hi设fi,j表示前i块水晶，两塔高度差为j时较高的那个塔的高度。 DP方程:fi,j=maxfi-1,j,fi-1,j+hi,fi-1,hi-j+j (j=hi)解析：fi-1,j 表示不放第i块水晶;fi-1,j+hi 表示第i块水晶放到了较矮的那个塔上，而且矮塔仍然为矮塔，填补了高度差；fi-1,hi-j+j 表示第i块水晶放到了较矮的那个塔上，但是矮塔变成了高塔；fi-1,j-hi+hi 表示第i块水晶放到了较高的塔上，增加了高度差；边界条件： 如果刚开始的f值都为0的话，调试的时候会发现，有许多不合逻辑的答案，例如:h1=1,f1,2也会算出值为1，但其实是无法用高度为1的水晶搭出高度差大于等于2的双塔的。 所以要把所先把所有的f赋成-maxlongint，然后f0,0:=0。var f:array0.100,0.2000of integer;n,sum,i,j,k:integer;h:array1.100of integer;function max(x,y,z:integer):integer;beginmax:=x;if maxy then max:=y;if maxz then max:=z;end;beginreadln(n);sum:=0;for i:=1 to n dobeginread(hi);sum:=sum+hi;end;for i:=0 to n dofor j:=0 to sum do fi,j:=-1000;f0,0:=0;for i:=1 to n dofor j:=0 to sum do begin if hi0 thenwrite(fn,0)elsewrite(Impossible);end.12、垃圾处理、任务分配有两行数，每行N个，每列选1个，共选N个数，将每行所选的数相加，结果取两个和的最大值，求这个最大值的最小值。样例输入：5 /每行N个数，以下两行2 4 1 4 5 /ai2 1 3 4 1 /bi输出：5第一行取3、4列，第二行取1、2、5列设Fi,j表示：完成前i项任务，若第1个人花了j分钟，那么第二个人最少花Fi,j分钟。F2,0=3F2,1=3F2,2=1F2,3=1F2,4=1F2,6=0.F2,20=0下面求F3，0=6F3，1 可以用两种方法的最小值来表示：（1） 第3件任务第一个人不做，则为 F2，1+B3（2） 第3件任务第一个人做，前提是时间够用，即j=ai,则为 F2,0那么有以下DP方程：Fi,j=MinFi-1,j+Bi,Fi-1,j-Ai边界F0,0=0,13、NOP2000方格取数（一）问题描述 设有NN的方格图（N8），我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0。如下图所示（见样例）： 向右A1234567810000000020013006003000070004000140000 向 下502100040060015000007014000000800000000B 某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。 输 入 输入的第一行为一个整数N（表示NN的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。 输 出 只需输出一个整数，表示2条路径上取得的最大的和。 样 例 输入 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 输出 67（二） 问题分析 本题是从1997年国际信息学奥林匹克的障碍物探测器一题简化而来，如果人只能从A点到B点走一次，就是以前的树塔问题，可以用动态规划算法求出从A点到B点的最优路径。具体的算法描述如下：从A点开始，向右和向下递推，依次求出从A点出发到达当前位置（i，j）所能取得的最大的数之和，存放在sum数组中，原始数据经过转换后用二维数组data存储，为方便处理，对数组sum和data加进零行与零列，并置它们的零行与零列元素为0。易知sumi，j= datai，j 当i=0或j=0 max（sumi-1，j，sumi，j-1）+ datai，j 当i0,且j0summ,n就是最大值，如果要求出具体的走法，可以通过倒推求得，具体算法如下： 置sum数组零行与零列元素为0 for i:=1 to n do for j:=1 to n do if sumi-1,jsumi,j-1 then sumi,j:=sumi-1,j+datai,j else sumi,j:=sumi,j-1+datai,j; /产生sum数组的值 i:=n; j:=n; while (i1) or (j1) do /以下是求具体的取法 if (i1) and (sumi,j=sumi-1,j+datai,j) then begin datai,j:=-1; i:=i-1 end else begin datai,j:=-1; j:=j-1 end; data1,1:=-1; 凡是被标上-1的格子即构成了从A点到B点的一条最优路径。那么是否可以按最优路径连续走两次而取得最大数和呢?这是一种很自然的想法,并且对样例而言也是正确的, 虽然这一算法保证了连续的两次走法都是最优的，但却不能保证总体最优，相应的反例也不难给出，请看下图： 图二按最优路径走一次后，余下的两个数2和3就不可能同时取倒了，而按图三中的非最优路径走一次后却能取得全部的数，这是因为两次走法之间的协作是十分重要的，而图2中的走法并不能考虑全局，因此这一算法只能算是“贪心算法”。虽然在一些情况下，贪心算法也能够产生最优解，但总的来说“贪心算法”是一种有明显缺陷的算法。实际上本问题完全可以用动态规划解决，只是递推起来更为复杂些而已，前面在考虑只走一次的情况，只需考虑一个人到达某个格子（i，j）的情况，得出sumi，j=max（sumi-1，j，sumi，j-1）+datai，j，现在考虑两个人同时从A出发，则需考虑两个人到达任意两个格子(i1，j1)与(i2，j2)的情况，显然要到达这两个格子，其前一状态必为下列四种情况之一：（2，4）、（2，3）、（1，4）、（1，3）坐标如下：（1）、(i1-1，j1)，(i2-1，j2)；（2）、(i1-1，j1)，(i2，j2-1)；（3）、(i1，j1-1)，(i2-1，j2)；（4）、(i1，j1-1)，(i2，j2-1)；用一个四维数组sumi1,j1,i2,j2来表示到达i1,j1与i2,j2时的最大值，设p=max(sumi1-1,j1,i2-1,j2,sumi1-1,j1,i2,j2-1,sumi1,j1-1,i2-1,j2,sumi1,j1-1,i2,j2-1)，则sumi1,j1,i2,j2= 0 当i1=0或j1=0或i2=0或j2=0 p + datai1,j1 当i1,j1,i2,j2均不为零，且i1=i2，j1=j2 p + datai1,j1+datai2,j2 当i1,j1,i2,j2均不为零,且i1i2或j1j2 （三）程序清单const maxn=10;type arraytype=array 0.maxn,0.maxn of longint;var i,j,k,n,i1,i2,j1,j2:longint; data:arraytype; sum:array 0.maxn,0.maxn,0.maxn,0.maxn of longint;function max(x,y:longint):longint;begin if xy then max:=x else max:=y;end;BEGIN for i:=1 to maxn do for j:=1 to maxn do datai,j:=0; readln(n); repeat readln(i,j,k); datai,j:=k until (i=0) and (j=0) and (k=0); fillchar(sum,sizeof(sum),0); for i1:=1 to n do for j1:=1 to n do for i2:=1 to n do for j2:=1 to n do begin sumi1,j1,i2,j2:=max(sumi1-1,j1,i2-1,j2,sumi1,j1,i2,j2); sumi1,j1,i2,j2:=max(sumi1-1,j1,i2,j2-1,sumi1,j1,i2,j2); sumi1,j1,i2,j2:=max(sumi1,j1-1,i2-1,j2,sumi1,j1,i2,j2); sumi1,j1,i2,j2:=max(sumi1,j1-1,i2,j2-1,sumi1,j1,i2,j2); sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai1,j1; /加上i1,j1 if (i1i2) or (j1j2) /两点不同的时候再加上i2,j2 then sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai2,j2 end; writeln(sumn,n,n,n)END.NOIP2008传纸条【问题描述】小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递