# P1004 grid access (two-state DP & four-dimensional DP)

2021-08-10 08:05:26

## P1004 Take the number of squares ( Two states DP& 4 d DP）

Subject portal

Ideas ： Because the optimal values of the two paths will affect each other , Therefore, choosing the optimal scheme at the same time is the correct solution , This ensures that a number will not be added twice . If you walk twice, it may not be the best solution （ Because the first time will affect the second plan ） Complexity O(9^4) It's still very small . Because it's a scrolling array , So it can be reduced to three dimensions , But it is not necessary to .

AC Code ：

``````#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[10][10][10][10],a[10][10];
int main(){
int n,x,y,v;
scanf("%d",&n);
while(scanf("%d%d%d",&x,&y,&v)){
if(!x&&!y&&!v) break;
a[x][y]=v;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
for(int l=1;l<=n;l++)
{		// Take the maximum value of the four states .
int tmp=max({dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]});
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];// duplicate removal
}
printf("%d\n",dp[n][n][n][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.
24.
```

https://chowdera.com/2021/08/20210810080205643d.html