NOIP2000 方格取数

题四．方格取数（33分）

问题描述

设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：

某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

输入

输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。

输出

只需输出一个整数，表示2条路径上取得的最大的和。

样例 ：

输入

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

输出

【思路】

DP。

同08年传纸条。如下：

最简单的思路是四维表示状态，两个纸条同时从11出发传递。方程：

d[i][j][ii][jj]=max{d[i-1][j][ii-1][jj],d[i-1][j][ii][jj-1],d[i][j-1][ii-1][jj],d[i][j-1][ii][jj-1]}+tmp;

tmp=(ii==i &&j==jj)?:a[i][j]: a[i][j]+a[ii][jj] //保证不重合

优化：两个一块传，可以知道两者的总步数是相等的，i+j=ii+jj根据这个结论可以减少一维的枚举。

另一种方法：三维表示状态。D[i][j][k]表示两者都走了i步且横坐标分别为jk。方程：

f[i][j][k]=max(f[i-1][j-1][k-1],f[i-1][j-1][k],f[i-1][j][k-1],f[i-1][j][k])+a[j][i-j+1]+a[k][i-k+1];

【代码

#include<iostream>
using namespace std;

const int maxn = 15;
int map[maxn][maxn];
int d[maxn][maxn][maxn][maxn];
int n;

int main() {
    ios::sync_with_stdio(false);
    cin>>n; int u,v,w;
    while(cin>>u>>v>>w) {
        if(!u && !v && !w) break;
        map[u][v]=w;
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++) {
            int l=i+j-k; if(l<1 || l>n) continue;
            int &ans=d[i][j][k][l];
            ans=max(max(d[i-1][j][k-1][l],d[i-1][j][k][l-1]),max(d[i][j-1][k-1][l],d[i][j-1][k][l-1]));
            ans += map[i][j]+map[k][l];
            if(i==k && j==l) ans-=map[i][j];
        }
    cout<<d[n][n][n][n];
    return 0;
}

】