当前位置:网站首页>P1006 传纸条 (双状态DP)

P1006 传纸条 (双状态DP)

2021-08-10 08:02:48 wx6110fa547fd20

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

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.

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

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328282