P1006 传纸条 (双状态DP）
P1006 传纸条 (双状态DP）
Harris-H
原创文章 147获赞 130访问量 6437
关注
私信
展开阅读全文
作者：Harris-H
题目传送门
思路：与P1004类似，也可以用四维，不过可以用三维记录步数即可完成状态转移。具体看代码。
四维AC代码：
#include
#include
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
#include
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;
}
Harris-H
原创文章 147获赞 130访问量 6437
关注
私信
展开阅读全文
作者：Harris-H
