P1004 [noip2000 improvement group] grid access

Title Description

Equipped with  N×N  The grid of (N≤9), Let's fill some of these squares with positive integers , And the other squares put numbers  0. As shown in the figure below （ See Example ）:

A
 0  0  0  0  0  0  0  0
 0  0 13  0  0  6  0  0
 0  0  0  0  7  0  0  0
 0  0  0 14  0  0  0  0
 0 21  0  0  0  4  0  0
 0  0 15  0  0  0  0  0
 0 14  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
                         B

Someone from the top left corner of the picture  A  Leaves at , You can walk down , You can also go right , Until we get to the bottom right  B  spot . On the way , He can take the number of squares （ The removed squares will be changed to numbers  0）.
This person is from  A  Point to  B  I'll walk two times , Try to find out  2  There are such paths , Make the sum of the numbers obtained the largest .

Input format

The first line of input is an integer  N（ Express N×N  The grid of ）, Each of the next lines has three integers , The first two represent positions , The third number is the number placed in the position . A single line  0  End of input .

Output format

Just output an integer , Express  2  The largest sum of the paths .

I/o sample

Input #1                                                                                           Output #1      

8                                                         67
2 3 13
2 6  6
3 5  7
4 4 14
5 2 21
5 6  4
6 3 15
7 2 14
0 0  0

explain / Tips

NOIP 2000 Improve group 4

Their thinking

This problem can be completed by dynamic gauge , Deep search should be no problem . This problem is solved by dynamic rules , First of all, we must consider the state transition equation of this problem , Because it is 2 Paths , We will find that this problem can't be completed with a simple two-dimensional array , If you write two two-dimensional arrays, it will inevitably timeout , Therefore, priority should be given to using four-dimensional arrays . You can write the shape transfer equation

f[i][j][k][m] = max(max(f[i - 1][j][k - 1][m], f[i][j - 1][k][m - 1]),max(f[i - 1][j][k][m - 1], f[i][j - 1][k - 1][m])) + d[i][j]

What does this equation of state mean , The path can only go down or to the right , Therefore, the optimal solution to reach a certain position is the maximum value above or on the left plus the number of this position , By two paths , So it's the largest of the four , Of course, just add d[ i ][ j ] It's not enough. , Because there's more d[ k ][ m ], But this is not optional , When i==k also j==m when , It indicates that the positions of the two paths coincide , Because the title says that the numbers should be taken after the process , So we can't add d[ k ][ m ], Otherwise, you have to add d[ k ][ m ].

Code

#include<iostream>

using namespace std;
int n, i, j, k, m, x, y, data;
int d[10][10], f[10][10][10][10];

int main() {
    cin >> n;
    while (cin >> x >> y >> data && !(!x && !y && !data))   // When x=0,y=0,data=0 To exit the loop 
        d[x][y] = data;
    for (i = 1; i <= n; i++)    // Traverse 
        for (j = 1; j <= n; j++)
            for (k = 1; k <= n; k++)
                for (m = 1; m <= n; m++) {
                    f[i][j][k][m] = max(max(f[i - 1][j][k - 1][m], f[i][j - 1][k][m - 1]),
                                        max(f[i - 1][j][k][m - 1], f[i][j - 1][k - 1][m])) + d[i][j];
                    if (i != k && j != m) f[i][j][k][m] += d[k][m];
                }
    cout << f[n][n][n][n];
}

  Of course, do you think this is over ？ The fourth dimension is still too slow , Maybe the data of this question is not very big , can AC. In fact, this problem can also be compressed to three dimensions . Start both paths at the same time , Therefore, the number of steps taken by the two paths is always equal , And from A To B You need to 2n Step , At this time, our equation of state is

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

  At this time i It means leaving i Step , and j It's the path a Go down j Step ,k Is the path b Go down k Step , that i-j It represents the path at this time a The abscissa reached ,i-k It represents the path at this time b The abscissa reached , Same as the four-dimensional time , When j==k when , It means that at this time, the places where the path passes coincide , No, just add a value , otherwise , I need to add d[ j ]d[ i-j ].

Optimize the code

#include <iostream>
using namespace std;
int n, i, j, k, x, y, data;
int d[10][10];
int f[20][10][10];
int main() {
    cin >> n;
    while (cin >> x >> y >> data && !(!x && !y && !data))   // When x=0,y=0,data=0 To exit the loop 
        d[x][y] = data;
    for (i = 1; i <= 2 * n; i++)
    {
        for (j = 1; j <= i && j <= n; j++) {
            for (k = 1; k <= i && k <= n; k++) {
                f[i][j][k] = d[i - k][k] +max(max(f[i - 1][j][k], f[i - 1][j - 1][k - 1]),
                                 max(f[i - 1][j - 1][k], f[i - 1][j][k - 1]));
                if (j != k)f[i][j][k] += d[i-j][j];
            }
        }
    }
    cout << f[2 * n][n][n];
}

by CJL