# P1006 paper transfer note (dual state DP)

2021-08-10 08:05:20

## P1006 Pass slip ( Two states DP）

Subject portal

Ideas ： And P1004 similar , You can also use four dimensions , However, the state transition can be completed by three-dimensional recording steps . See code for details .

4 d AC Code ：

``````#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.
```

The three dimensional AC Code ：

``````#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];// Here is the assumption that two people from （0,1) and （1,0) Start walking
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.
```

https://chowdera.com/2021/08/20210810080205637X.html