P1004 方格取数

feecle6418 · 2017-12-08 20:29:41 · 题解

这题，是四维动规的模板题，和P1006传纸条基本相似。

我们考虑两个人同时走，就相当于数字三角形。状态转移方程为：

不过要判断i=k&&j=l的情况。

完整代码如下：

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int f[12][12][12][12],a[12][12],n,x,y,z;
    int main() {
        cin>>n>>x>>y>>z;
        while(x!=0||y!=0||z!=0){
            a[x][y]=z;
            cin>>x>>y>>z;
        }
        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(max(f[i-1][j][k-1][l],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&&l==j)f[i][j][k][l]-=a[i][j];
                    }
                }
            }
        }
        cout<<f[n][n][n][n];
        return 0;
}