这篇文章上次修改于 694 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 803 个字，阅读时长 ≈ 3 分钟

AcWing 1027. 方格取数

洛谷原题：P1004 方格取数

题面：

设有 $N \times N$ 的方格图 $(N \le 9)$，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 $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$ 条这样的路径，使得取得的数之和为最大。

这个的做法挺神奇的我感觉，是用一个四维的dp进行求解，用一个暴力的方法，进行同一时间的两个数字三角形模型的dp。如果两个dp的坐标重复要减去一个数，因为重复后同一个数取了两遍，第二遍应该为0。

#include<iostream>
using namespace std;
int n,x,y,v;
int a[20][20];
int f[20][20][20][20];
int main()
{
    cin>>n;
    do{
        cin>>x>>y>>v;
        a[x][y]=v;
    }while(x!=0);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            for(int k=1;k<=n;++k){
                for(int l=1;l<=n;++l){
                    f[i][j][k][l]=max(f[i-1][j][k-1][l],max(f[i-1][j][k][l-1],max(f[i][j-1][k-1][l],f[i][j-1][k][l-1])))+a[i][j]+a[k][l];
                    if(i==k&&j==l) f[i][j][k][l]-=a[i][j];
                }
            }
        }
    }
    cout<<f[n][n][n][n]<<endl;
    return 0;
}