题意
5103 传纸条 0x50「动态规划」例题
描述
给定一个 N*M 的矩阵A，每个格子中有一个整数。现在需要找到两条从左上角 (1,1) 到右下角 (N,M) 的路径，路径上的每一步只能向右或向下走。路径经过的格子中的数会被取走。两条路径不能经过同一个格子。求取得的数之和最大是多少。N,M≤50。
输入格式
第一行有2个用空格隔开的整数n和m，表示有n行m列（1<=n,m<=50）。
接下来的n行是一个n*m的矩阵，每行的n个整数之间用空格隔开。
输出格式
一个整数，表示答案。
样例输入
3 3 0 3 9 2 8 5 5 7 0
样例输出
34
数据范围与约定
- 30%的数据满足：1<=m,n<=10
100%的数据满足：1<=m,n<=50
来源
CCF NOIP2008 T3
分析
这种只能向右和向下走，只能在同时走到相同的格子，所以维护当前在哪个格子即可。容易设出状态\(F[x_1,y_1,x_2,y_2]\)，但是这些状态并不都合法。只有\(x_1+y_1=x_2+y_2\)时状态才合法，这启示我们设立新的状态。
由于同一时间两条线路走的步数是相同的，而步数和行数就可以确定位置，所以可以用\(F[i,x_1,x_2]\)表示走了\(i\)步，第一条线走到了\(x_1\)行，第二条线走到了\(x_2\)行，已经取得的数的最大值。
那么枚举两条线路往哪走转移即可，注意判断走到了相同的格子。
时间复杂度\(O((n+m)n^2)\)
代码
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using std::max;
co int N=51;
int n,m,a[N][N],f[N*2][N][N];
int main(){
// freopen(".in","r",stdin),freopen(".out","w",stdout);
read(n),read(m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) read(a[i][j]);
for(int i=0;i<n+m-2;++i)
for(int j=1;j<=n&&j<=i+1;++j)
for(int k=1;k<=n&&k<=i+1;++k){
if(j==k){ // both right or down
f[i+1][j][k]=max(f[i+1][j][k],f[i][j][k]+a[j][i+3-j]);
f[i+1][j+1][k+1]=max(f[i+1][j+1][k+1],f[i][j][k]+a[j+1][i+2-j]);
}
else{
f[i+1][j][k]=max(f[i+1][j][k],f[i][j][k]+a[j][i+3-j]+a[k][i+3-k]);
f[i+1][j+1][k+1]=max(f[i+1][j+1][k+1],f[i][j][k]+a[j+1][i+2-j]+a[k+1][i+2-k]);
}
if(j+1==k) f[i+1][j+1][k]=max(f[i+1][j+1][k],f[i][j][k]+a[j+1][i+2-j]); // j down, k right
else f[i+1][j+1][k]=max(f[i+1][j+1][k],f[i][j][k]+a[j+1][i+2-j]+a[k][i+3-k]);
if(k+1==j) f[i+1][j][k+1]=max(f[i+1][j][k+1],f[i][j][k]+a[j][i+3-j]); // j right,k down
else f[i+1][j][k+1]=max(f[i+1][j][k+1],f[i][j][k]+a[j][i+3-j]+a[k+1][i+2-k]);
}
printf("%d\n",f[n+m-2][n][n]);
return 0;
}