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; }