题解：P1004 [NOIP2000 提高组] 方格取数

· · 题解

经典动态规划题目，本篇题解使用的是三维 dp。

由于要走两遍，所以我们直接处理两条路径。设 dp_{i_1,j_1,i_2,j_2} 表示走了 i_1+j_1 步，第一条路径走到 (i_1,j_1)，第二条路径走到 (i_2,j_2) 的最大取数之和。显然有 i_1+j_1=i_2+j_2，因此 j_2 一维可以压掉。

如果两条路径走到同一格，那么当前格子只能加一次。有状态转移方程 dp_{i_1,j_1,i_2}=\begin{cases}sc_{i_1,j_1}+\max(dp_{i_1,j_1-1,i_2-1},dp_{i_1-1,j_1,i_2}) & i_1=i_2\\sc_{i_1,j_1}+sc_{i_2,i_1+j_1-i_2}+\max(dp_{i_1-1,j_1,i_2-1},dp_{i_1-1,j_1,i_2},dp_{i_1,j_1-1,i_2-1},dp_{i_1,j_1-1,i_2}) & i_1\ne i_2\end{cases}。

其中 sc_{i,j} 表示 (i,j) 格上的数。

#include<bits/stdc++.h>
using namespace std;

const int N=12;
int sc[N][N];
int dp[N][N][N]; 

int main(){
    int n;cin>>n;int x,y,z;
    while(cin>>x>>y>>z){
        if(!(x || y || z)) break;
        sc[x][y]=z;
    }
    for(int i1=1; i1<=n; i1++){
        for(int j1=1; j1<=n; j1++){
            for(int i2=1; i2<=i1+j1-1; i2++){
                if(i1==i2) dp[i1][j1][i2]=sc[i1][j1]+max(dp[i1][j1-1][i2-1],dp[i1-1][j1][i2]);
                else dp[i1][j1][i2]=sc[i1][j1]+sc[i2][i1+j1-i2]+max({dp[i1-1][j1][i2-1],dp[i1-1][j1][i2],dp[i1][j1-1][i2-1],dp[i1][j1-1][i2]});
//              cout<<i1<<" "<<j1<<" "<<i2<<" "<<dp[i1][j1][i2]<<"\n";
            }
//          cout<<"\n";
        }
    }
    cout<<dp[n][n][n];
    return 0;
}

因为两条路径长度相同，所以第二条路径一定不会走到第一条路径曾经过的点。所以是否将第一条路径上经过的点上的数赋零对答案无影响。