CF213C (棋盘dp的经典例题)

Relay Race - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本题是棋盘dp的经典例题。

可以先转化一下题意：从(1,1)走两条路径到(n,n)，再确保两人是同步行走的。

我们可以让一人的走路范围一直在左下方向，一人的走路范围一直在右上方向。（倘若两人的路径交叉，则都可以转化成这种情况）

令dp[i][j][k][l] 表示 第一个人走到(i,j) 第二个人走到(k,l) 能获得最大的值.但这空间复杂度会爆炸

注意到 i+j=k+l (因为是两人是同步的，时间一样)

令 i+j=k+l=tot

则 dp[tot][i][k]表示第一个人走到(i,tot-i),第二个人走到(k,tot-k)能获得的最大的值

dp转移:考虑dp[tot][i][j]从何转移过来(此时为走到(i,tot-i)和(j,tot-j))

如果 i==j，此时走到同一个点，此点的贡献只能算一次要特判：

dp[tot][i][j]=max({dp[tot-1][i][j],dp[tot-1][i-1][j],dp[tot-1][i][j-1],dp[tot-1][i-1][j]})+a[i][j];

否则两人便是走到不同的点，各自贡献答案：

dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i][j]+a[i][tot-i]+a[j][tot-j]);

dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i-1][j]+a[i][tot-i]+a[j][tot-j]);

dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i][j-1]+a[i][tot-i]+a[j][tot-j]);

dp[tot][i][j]=max(dp[tot][i][j],dp[tot-1][i-1][j-1]+a[i][tot-i]+a[j][tot-j]);

 第一维可以滚动数组来优化空间复杂度，记得要及时更新不合法的状态。

初始化:dp[0][1][1]=a[1],(原本是dp[2][1][1]=a[1],但是滚动数组要%2)，其余都为-INF

答案:dp[2*n%2][n][n]

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
const int N=310;
//const int M=;
//const int inf=1e9;
const ll INF=1e18;
int T,n,a[N][N];
ll dp[3][N][N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); 
    n=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) a[i][j]=read();
    for(int i=0;i<2;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
                dp[i][j][k]=-INF;
    dp[0][1][1]=a[1][1];
    for(int tot=3;tot<=2*n;tot++)
    {
        for(int i=1;i<=tot-1;i++)
            for(int j=1;j<=tot-1&&j<=i;j++)
            {
                //走到a[i][tot-i]和a[j][tot-j] 
                if(i==j) dp[tot%2][i][j]=max({dp[(tot-1)%2][i-1][j],dp[(tot-1)%2][i][j-1],dp[(tot-1)%2][i-1][j-1],dp[(tot-1)%2][i][j]})+a[i][tot-i];
                else
                {
                    dp[tot%2][i][j]=max(dp[tot%2][i][j],dp[(tot-1)%2][i-1][j]+a[i][tot-i]+a[j][tot-j]);
                    dp[tot%2][i][j]=max(dp[tot%2][i][j],dp[(tot-1)%2][i][j-1]+a[i][tot-i]+a[j][tot-j]);
                    dp[tot%2][i][j]=max(dp[tot%2][i][j],dp[(tot-1)%2][i-1][j-1]+a[i][tot-i]+a[j][tot-j]);
                    dp[tot%2][i][j]=max(dp[tot%2][i][j],dp[(tot-1)%2][i][j]+a[i][tot-i]+a[j][tot-j]);
                }
            }
        for(int i=1;i<=tot-1;i++)
            for(int j=1;j<=tot-1&&j<=i;j++)
                dp[(tot-1)%2][i][j]=-INF;
    }

    printf("%lld",dp[(2*n)%2][n][n]);
    return 0;
}