[Acwing 1027] 方格取数（三维DP）

题链

题意

N*N的方格，某些方格填入正整数，其他方格为0，左上角入口，右下角为出口，走过的路上可以取方格中的数，取完变为0，只能向右和下走，走两次，求两次取得的数字和的最大值。

思路

一个人走两次，数只能取一次，可以想象成两个人同时走。用四维状态\((x_1,y_1,x_2,y_2)\)表示两个人当前的坐标，数只能取一次，那么两个人走的先后顺序不影响最后结果，假设两个人同时走，那么同一时刻两人的步数是一样的（\(k^{'}=(x_1-1+y_1-1)=(x_2-1+y_2-1)\)），不妨假设\(k=(x_1+y_1)=(x_2+y_2)\)，那么可以将四维降成三维\((k,x_1,x_2)\)，递推同时考虑两个人，如果两个人某一时刻走到同一个格子，那么满足\((x_1=x_2)\)，那么这个格子的值只能加一次，否则dp值加上两个人当期位置的格子的值。最后结果为\(dp[n+n][n][n]\)

Code:

#include <bits/stdc++.h>
using namespace std;
#define fre freopen("data.in","r",stdin);
#define ms(a) memset((a),0,sizeof(a))
#define go(i,a,b) for(register int (i)=(a);(i)<(b);++(i))
#define rep(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
#define sf(x) scanf("%d",&(x))
#define reg register
typedef long long LL;
const int inf=(0x7f7f7f7f);
const int maxn=1e5+5;
int n,x,y,w;
int a[12][12];
int dp[30][12][12];
int main(){
    sf(n);
    while(scanf("%d%d%d",&x,&y,&w)==3&&x&&y&&w)a[x][y]=w;
    int j1,j2;
    rep(k,2,n+n)
    rep(i1,1,n)
    rep(i2,1,n){
        j1=k-i1,j2=k-i2;
        if(j1<1||j1>n||j2<1||j2>n)continue;

        int t=a[i1][j1];
        if(j1!=j2)t+=a[i2][j2];
        int &x=dp[k][i1][i2];
        x=max(x,dp[k-1][i1-1][i2-1]+t);
        x=max(x,dp[k-1][i1][i2-1]+t);
        x=max(x,dp[k-1][i1-1][i2]+t);
        x=max(x,dp[k-1][i1][i2]+t);
    }
    printf("%d\n",dp[n+n][n][n]);
    return 0;
}

# [Acwing 1027] 方格取数（三维DP）