方格取数

如履薄冰 · 2025-01-27 12:04:01 · 题解

解法

考虑使用三维动态规划，使用最基础的动态规划跑两遍明显过不了。首先我们要解决一个问题：如何避免一个格子被拿两遍？我们可以同时遍历两个路径。我们设第一条路径目前的横坐标为 i，纵坐标为 j。再设第二条路径目前的横坐标为 k，纵坐标为 l。不难发现 i+j 一定等于 k+l。因为他们的坐标总和只能在每一步中加一，而这两个坐标又是同时移动的。这样就需要四个维度。我们可以进行降维优化。接下来我要重新定义一些上文定义过的变量，请勿参考上文的变量来理解下文的变量。我们可以设 i 为我们现在总共走的步数，设 j 为第一条路径目前的横坐标，再设 k 为第二条路径目前的横坐标。我们可以设一个三维数组 dp 用来存储相应的状态，进行状态转移。状态转移方程十分好推，这里就不给出了，如果真的不知道状态转移方程是什么，就去看我的代码，我的代码中间有个三重循环，这个三重循环里面就是状态转移方程的实现部分。最终答案为 dp_{n \times 2,n,n}。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,dp[110][110][110],mp[1100][1100];
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    while(true){
        int x,y,num;
        cin>>x>>y>>num;
        if(x==0&&y==0&&num==0){
            break;
        }else{
            mp[x][y]=num;
        }
    }
    for(int i=2;i<=n*2;i++){
        for(int j=max(i-n,1ll);j<=min(n,i-1);j++){
            for(int k=max(i-n,1ll);k<=min(n,i-1);k++){
                dp[i][j][k]=max(max(max(dp[i-1][j][k],dp[i-1][j-1][k-1]),dp[i-1][j][k-1]),dp[i-1][j-1][k]);
                dp[i][j][k]+=mp[j][i-j];
                if(j!=k){
                    dp[i][j][k]+=mp[k][i-k];
                }
            }
        }
    }
    cout<<dp[n*2][n][n];
    return 0;
}