这篇文章上次修改于 703 天前,可能其部分内容已经发生变化,如有疑问可询问作者。
本文共 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;
}