# 2853 checkerboard game (3D board)

2021-07-21 19:08:36

The time limit : 1 s
Space restriction : 128000 KB
Question level : diamond Diamond
View the run results

Title Description   Description

Cai Cai sees a game , It's called the game of squares ~

The rules of the game are like this ：

In a n*n In the grid of , At every 1*1 You can get a certain number of bonus points in every grid , Note that the upper left corner is (1,1), The lower right corner is (n,n). Players need to choose one (1,1) To (n,n) The path of , And get bonus points on the path . Of course, there are also requirements for the path , The requirement is that we can only go in the direction of larger coordinates 【 from (x,y) To (x+1,y) perhaps (x,y+1)】, through 2n-1 There are three areas to reach (n,n). Of course , The one with the highest score will win .

At this time , Cai Cai sees his good friend Yueyue , So I invited her to play the double version . The rule of the double version is to add a line on the basis of the single version. The two people's route can't be the same . Yueyue knows that Cai Cai is very smart , I'm afraid I'll lose too badly , I don't want to play with him . Vegetables are in a panic , So we define a fair value D, The fair value is equal to the sum of the absolute value of the difference between the points one by one corresponding to the subtraction that can be obtained by the path chosen by the two people , namely D=sigma (|kxi-kyi|)|(kx,ky They are vegetables , The jungle coefficient of every area that the moon passes through ）. But it's a huge computing task , Caicai found you , Please help to calculate the maximum value of fair value .

Input description   Input Description

first line , A positive integer n

Next n That's ok , Each row n It's an integer , Represents the fair value of each area in the jungle

Output description   Output Description

An integer Dmax, That is, the maximum value of fair value

The sample input   Sample Input

4

1 2 3 4

1 5 3 2

8 1 3 4

3 2 1 5

Sample output   Sample Output

13

Data range and tips   Data Size & Hint

about 20% The data of , Guarantee 0＜n≤20

about 50% The data of , Guarantee 0＜n≤50

about 100% The data of , Guarantee 0＜n≤100 And for all i,j Guarantee |Kij|≤300

First of all, this four-dimensional problem will explode space .

So I learned to use three-dimensional representation .

Premise ：

1. Let the coordinates of two people be A,B;

2.n*n Of the lattice , from (1,1) Point to (n,n) The total number of steps required for the point is 2*n+1（n Geheng ,n Columns , There's a repetition ）

We use it k To represent the number of steps

We use it i To show that in the second k Step A The abscissa of is i

use j To show that in the second k Step B The abscissa of is j

that A The coordinates of can be expressed as （i,k-i+1）

B The coordinates of can be expressed as （j,k-j+1）

For each of these points （i,j）

There are also four cases transferred from

1.A From top to bottom 　　　　dp[i-1][j][k-1]

2.B From top to bottom 　　　　dp[i][j-1][k-1]

3.ＡＢ At the same time, from top to bottom dp[i-1][j-1][k-1]

４．ＡＢ At the same time, from left to right dp[i][j][k-1]

And then add in the value of this point

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<cstdlib>
6 using namespace std;
8 {
9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9')
11     {c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9')
13     {x=x*10+(c-48);c=getchar();}
14     flag==1?n=-x:n=x;
15 }
16 int n;
17 int dp[101][101][301];
18 int a[101][101];
19 int ans=0;
20 int main()
21 {
23     for(int i=1;i<=n;i++)
24         for(int j=1;j<=n;j++)
26     // a :(i,k-i+1)
27     // b :(j,k-j+1)
28     for(int k=1;k<=2*n-1;k++)
29     {
30         for(int i=1;i<=n&&i<=k;i++)
31             for(int j=1;j<=n&&j<=k;j++)
32             {
33                 dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j][k]);
34                 dp[i][j][k]=max(dp[i][j-1][k-1],dp[i][j][k]);
35                 dp[i][j][k]=max(dp[i-1][j-1][k-1],dp[i][j][k]);
36                 dp[i][j][k]=max(dp[i][j][k-1],dp[i][j][k]);
37                 dp[i][j][k]+=abs(a[i][k-i+1]-a[j][k-j+1]);
38             }
39     }
40     printf("%d",dp[n][n][2*n-1]);
41     return 0;
42 }```

https://chowdera.com/2021/06/20210604213017082v.html