1169 传纸条动态规划

四位DP:

利用f[i1][j1][i2][j2]记录第一个人走在i1,j1 的位置，第二个人走在i2, j2的位置，最大值

[cpp]

#include

#define max(a,b) a>b a:b

using namespace std;

int m,n;

int a[51][51];

int dp[51][51][51][51];

int main(){

int i,j,i1,i2,j1,j2;

scanf("%d%d",&m,&n);

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

scanf("%d",&a[i][j]);

for(i1=1;i1<=m;i1++)

for(j1=1;j1<=n;j1++)

for(i2=1;i2<=m;i2++)

for(j2=1;j2<=n;j2++){

int p1=max(dp[i1-1][j1][i2-1][j2],dp[i1-1][j1][i2][j2-1]);

int p2=max(dp[i1][j1-1][i2-1][j2],dp[i1][j1-1][i2][j2-1]);

int p=max(p1,p2);

if(i1==i2&&j1==j2)

dp[i1][j1][i2][j2]=p+a[i1][j1];

else

dp[i1][j1][i2][j2]=p+a[i1][j1]+a[i2][j2];

}

printf("%d\n",dp[m][n][m][n]);

return 0;

}

三维DP:

考虑到两个人走的总步数都相等，利用f[k][i][j]表示第一个人在一个方向上走了i步，另外一个人在相同方向上走了j步的最大值。

[cpp]

#include

#define max(a,b) a>b a:b

#define min(a,b) a
using namespace std;

int m,n;

int a[51][51];

/*

int dp[51][51][51];

int main(){

int i,j,i1,i2,j1,j2;

scanf("%d%d",&m,&n);

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

scanf("%d",&a[i][j]);

for(i1=1;i1<=m;i1++)

for(j1=1;j1<=n;j1++)

for(i2=1;i2<=m;i2++){

//for(j2=1;j2<=n;j2++){

int p1=max(dp[i1-1][j1][i2-1],dp[i1-1][j1][i2]);

int p2=max(dp[i1][j1-1][i2-1],dp[i1][j1-1][i2]);

int p=max(p1,p2);

if(i1==i2&&j1==(i1+i2-j1))

dp[i1][j1][i2]=p+a[i1][j1];

else

dp[i1][j1][i2]=p+a[i1][j1]+a[i2][(i1+i2-j1)];

}

//}

printf("%d\n",dp[m][n][m]);

return 0;

}

*/

int f[101][51][51];

int main(){

int i,j,k,s,t,p=0;

scanf("%d%d",&m,&n);

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

scanf("%d",&a[i][j]);

for(i=1;i<=m+n-1;i++){

s=min(n,i);

t=min(m,i);

for(j=i-s+1;j<=t;j++)//j means that the first person has walked j steps;

for(k=i-s+1;k<=t;k++)//k means that the second person has walked k steps

if(j!=k||i+1==m+n){//For (1,1), the person has walked 1 step. So for (m,n), the person has walked m+n-1 steps

p=0;

p=max(p,f[i-1][j][k]);

p=max(p,f[i-1][j-1][k]);

p=max(p,f[i-1][j][k-1]);

p=max(p,f[i-1][j-1][k-1]);

f[i][j][k]=p+a[j][i-j+1]+a[k][i-k+1];

}

}

printf("%d\n",f[m+n-1][m][m]);

return 0;

}

1169 传纸条 动态规划