P1006 传纸条 (双状态DP）

题目传送门

思路：与P1004类似，也可以用四维，不过可以用三维记录步数即可完成状态转移。具体看代码。

四维AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=55;
int dp[N][N][N][N],a[N][N];
int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=m;k++)
				for(int l=1;l<=n;l++)
				{
					int  tmp=max({dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k][l-1],dp[i][j-1][k-1][l]});
					dp[i][j][k][l]+=tmp+a[i][j]+a[k][l];
					if(i==k&&j==l) dp[i][j][k][l]-=a[i][j];
				}
		printf("%d\n",dp[m][n][m][n]);
	return 0; 
}

三维AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=55;
int dp[N<<1][N][N],a[N][N];
int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	dp[1][1][1]=a[1][1];//这里是假设两个人从（0，1)和（1，0)开始走
	for(int k=2;k<=n+m-1;k++)
		for(int i=1;i<=m&&i<=k;i++)
			for(int j=1;j<=m&&j<=k;j++)
				{
					 int mx=max({dp[k-1][i][j],dp[k-1][i-1][j-1],dp[k-1][i][j-1],dp[k-1][i-1][j]});
					 dp[k][i][j]=mx+a[i][k+1-i]+a[j][k+1-j];
					 if(i==j) dp[k][i][j]-=a[i][k+1-j];
					 printf("dp[%d][%d][%d]=%d\n",k,i,j,dp[k][i][j]);
				}
		printf("%d\n",dp[n+m-1][m][m]);
	return 0; 
}