题目链接:
题目相当于从上向下走两次,首先可以想到一个Naive的DP:
设(f[a][b][c][d])表示一个人当前在((a,b)),另一个在((c,d))时取的最大值。
有一个显然的优化是只用保留(a+b=c+d)的状态(两人同时出发,速度相同)就可以求出答案。
那么有转移方程(f[a][b][c][d]=Max(f[a-1][b][c-1][d],f[a-1][b][c][d-1],f[a][b-1][c-1][d],f[a][b-1][c][d-1])+((a,c)=(b,d)?a[a][b]:a[a][b]+a[c][d]))
但是(n^4)是会爆炸的,我们需要再减少状态数。
发现若知道了(a,b,c),那么就可以求出(d=a+b-c),于是就可以去掉一维。
时间复杂度 (O(n^3))
空间复杂度 (O(n^3))
顺便这题行列输入是反的,莫名多WA一次
代码:
#include <cstdio>
inline int Max(const int a,const int b){return a>b?a:b;}
int m,n,w[205][205],f[205][205][205];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
scanf("%d",&w[i][j]);
for(int s=2;s<=n+m;++s)//枚举总步数a+b
for(int a=1;a<=m;++a)
for(int c=1;c<=m;++c)
{
int b=s-a,d=s-c;
if(b<1||b>n||d<1||d>n)continue;
int p1=Max(f[a-1][b][c-1],f[a-1][b][c]);
int p2=Max(f[a][b-1][c],f[a][b-1][c-1]);
f[a][b][c]=Max(p1,p2)+(a==c?w[a][b]:w[a][b]+w[c][d]);
}
printf("%d
",f[m][n][m]);
return 0;
}