方格取数(NOIP2000)

0

推荐

问题描述:
设有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
		13			6
				7
			14
	21				4
		15
	14
							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次取得最优。这样看来似乎不能用动态规划。

      其实，我们可以把一个人分两次取看成两个不同的人同时取，基于这个思想，只需稍做修改即可。
     一个人走一次的情况下，要到达(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)的状态，如图：

要经过这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)
 2program fangge02;
 3const maxn=10;
 4var
 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
 9procedure init;
10begin
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);
20end;
21
22procedure work;
23begin
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;
41end;
42
43begin
44    init;
45    work;
46    writeln('max=',sum[n,n,n,n]);
47end.