四位DP: 利用f[i1][j1][i2][j2]記錄第一個人走在i1,j1 的位置，第二個人走在i2, j2的位置，最大值 [cpp] #include<cstdio> #include<cstdlib> #include<algorithm> #include<map> #include<cstring> #include<cmath> #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<cstdio> #include<cstdlib> #include<algorithm> #include<map> #include<cstring> #include<cmath> #define max(a,b) a>b?a:b #define min(a,b) a<b?a:b 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; }
