问题描述: 设有N*N的方格图(N<=8),我们将其中的某些方格中填入正整数,而其他的方格中则放人数字0。如下图所示(见样例): A 0 0 0 0 0 0 0 0 0 0 13 0 0 6 0 0 0 0 0 0 7 0 0 0 0 0 0 14 0 0 0 0 0 21 0 0 0 4 0 0 0 0 15 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B
某人从图的左上角的A点出发,可以向下行走,也可以向右走,直到到达右下角的B 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。 此人从A点到B点共走两次,试找出2条这样的路径,使得取得的数之和为最大。 输入: 输入的第一行为一个整数N(表示N*N的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的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
分析: 此题与标准的方格取数(见http://www.cnblogs.com/gzydn/archive/2009/06/22/1508077.html)不同之处在于:要取2次,如果按照2次动态规划来取,每次都尽可能取最多,这样得不到最优的结果,因为第一次的取数会对第二次造成影响,即有后效性,如图,如果按照图2的方式走了第一次,则再也取不到2和3;如果按照图3的方式走了第一次,则能取到2次取得最优。这样看来似乎不能用动态规划。
![](http://image67.360doc.com/DownloadImg/2013/11/2717/37026745_1.jpg)
其实,我们可以把一个人分两次取看成两个不同的人同时取,基于这个思想,只需稍做修改即可。 一个人走一次的情况下,要到达(i,j)格子的前2个状态是:(i-1,j)、(i,j-1)状态方程为: sum[i,j]=max(sum[i-1,j],sum[i,j-1])+data(i,j) 边界是sum[i,j]=0 (i=0,j=0) 两个人同时走的情况下,需要考虑2个人到达任意两个格子(i1,j1)、(i2,j2)的状态,如图:
![](http://image67.360doc.com/DownloadImg/2013/11/2717/37026745_2.jpg) 要经过这2个格子,有这样的4种状态: (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]),则: 则 sum[i1,j1,i2,j2]= 0 当i1=0或j1=0或i2=0或j2=0 (边界) p + data[i1,j1] 当i1,j1,i2,j2均不为零,且i1=i2,j1=j2 (有重复路线) p + data[i1,j1]+data[i2,j2] 当i1,j1,i2,j2均不为零,且i1≠i2或j1≠j2 (无重复路线)
1 //方格取数(NOIP2000) 2 program fangge02; 3 const maxn=10; 4 var 5 i,j,k,n,i1,i2,j1,j2:longint; 6 data:array[0..maxn,0..maxn] of longint; 7 sum:array[0..maxn,0..maxn,0..maxn,0..maxn] of longint; 8![](http://image67.360doc.com/DownloadImg/2013/11/2717/37026745_3.gif) 9 procedure init; 10 begin 11 for i:=1 to maxn do 12 for j:=1 to maxn do 13 data[i,j]:=0; 14 readln(n); 15 repeat 16 readln(i,j,k); 17 data[i,j]:=k; 18 until(i=0)and(j=0)and(k=0); 19 fillchar(sum,sizeof(sum),0); 20 end; 21![](http://pubimage.360doc.com/wz/default.gif) 22 procedure work; 23 begin 24 for i1:=1 to n do //寻找到达(i1,j1,i2,j2)的4种状态的最大值 25 for j1:=1 to n do 26 for i2:=1 to n do 27 for j2:=1 to n do 28 begin 29 if sum[i1-1,j1,i2-1,j2]>sum[i1,j1,i2,j2] then 30 sum[i1,j1,i2,j2]:= sum[i1-1,j1,i2-1,j2]; 31 if sum[i1-1,j1,i2,j2-1]>sum[i1,j1,i2,j2] then 32 sum[i1,j1,i2,j2]:= sum[i1-1,j1,i2,j2-1]; 33 if sum[i1,j1-1,i2-1,j2]>sum[i1,j1,i2,j2] then 34 sum[i1,j1,i2,j2]:=sum[i1,j1-1,i2-1,j2]; 35 if sum[i1,j1-1,i2,j2-1]>sum[i1,j1,i2,j2] then 36 sum[i1,j1,i2,j2]:=sum[i1,j1-1,i2,j2-1]; 37 sum[i1,j1,i2,j2]:=sum[i1,j1,i2,j2]+data[i1,j1]; //有重复路线的时候 38 if(i1<>i2)or(j1<>j2) then 39 sum[i1,j1,i2,j2]:=sum[i1,j1,i2,j2]+data[i2,j2]; //没有重复路线 40 end; 41 end; 42![](http://pubimage.360doc.com/wz/default.gif) 43 begin 44 init; 45 work; 46 writeln('max=',sum[n,n,n,n]); 47 end.
|