Question link
[NOIP2000 Improvement Group] Square Number Retrieval
Title description
Equipped with
N
×
N
N \times N
N×N grid plot
(
N
≤
9
)
(N \le 9)
(N≤9), we fill some of the squares with positive integers, and other squares with numbers
0
0
0. As shown below (see example):
Someone from the upper left corner of the picture
A
A
Starting from point A, you can walk down or right until you reach the lower right corner
B
B
Point B. On the way, he can take away the numbers in the squares (the squares taken away will become numbers
0
0
0).
This person from
A
A
A point arrived
B
B
Go to point B twice and try to find out
2
2
2 such paths, such that the sum of the obtained numbers is the largest.
Input format
The first line of input is an integer
N
N
N (represents
N
×
N
N \times N
N×N grid), each subsequent row has three integers, the first two represent the position, and the third number is the number placed at the position. a separate line
0
0
0 indicates the end of input.
Output format
Just output an integer representing
2
2
The maximum sum obtained on 2 paths.
Example #1
Sample input #1
8 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
Sample Output #1
67
Algorithmic thinking (dynamic programming)
Algorithmic thinking (dynamic programming)
According to the title description, it is required to start from
(
1
,
1
)
(1,1)
(1,1)to
(
n
,
n
)
(n,n)
(n,n) traveled twice in total, try to find
2
2
2 such paths, such that the sum of the obtained numbers is the largest.
In the process of counting, each grid can only be counted once. Then there is such a property: except for the starting point and the end point, when the path has no intersection, the benefit will not be worse than when there is an intersection. For the proof method, please refer to another blog of the blogger: NOIP2005 Improvement Group Second Round T3: Passing the Note.
With the above properties, you can make two paths start from the upper left corner at the same time
A
A
Starting from point A, take one step at a time. Since you can only go down and to the right, you will eventually reach the lower right corner at the same time. Then it can be solved using the following dynamic programming ideas:
- Status representation:
f[x1,y1,x2,y2]means that after two paths have taken several steps at the same time, the first reaches(x1, y1), and the second The maximum value when the bar reaches(x2, y2). - The state calculation can be divided into the following steps according to the last step:
4
4
4 situations, take the maximum value:
- Moving right at the same time is,
f[x1,y1-1,x2,y2-1] + w[x1, y1] + w[x2, y2] - The first one goes right and the second one goes down,
f[x1,y1-1,x2-1,y2] + w[x1, y1] + w[x2, y2] - The first one goes down and the second one goes right,
f[x1-1,y1,x2,y2-1] + w[x1, y1] + w[x2, y2] - At the same time, the downward trend is:
f[x1-1, y1,x2-1,y2] + w[x1, y1] + w[x2, y2]
- Moving right at the same time is,
It should be noted that in the status calculation:
- If two paths lead to the same grid, the number in that grid can only be added
1
1
1 time
Time complexity
A total of
O
(
n
4
)
O(n^4)
O(n4) states, each state requires
O
(
1
)
O(1)
The amount of calculation is O(1), so the total time complexity is
O
(
n
4
)
O(n^4)
O(n4).
Code implementation
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int w[N][N], f[N][N][N][N];
int main()
{<!-- -->
int n, x, y, z;
cin >> n;
while(cin >> x >> y >> z, x || y || z) w[x][y] = z;
for(int x1 = 1; x1 <= n; x1 + + )
for(int y1 = 1; y1 <= n; y1 + + )
for(int x2 = 1; x2 <= n; x2 + + )
for(int y2 = 1; y2 <= n; y2 + + )
{<!-- -->
int t = max(max(f[x1][y1 - 1][x2][y2 - 1], f[x1][y1 - 1][x2 - 1][y2]),
max(f[x1 - 1][y1][x2 - 1][y2], f[x1 - 1][y1][x2][y2 - 1]));
if(x1 == x2 & amp; & amp; y1 == y2)
f[x1][y1][x2][y2] = t + w[x1][y1];
else
f[x1][y1][x2][y2] = t + w[x1][y1] + w[x2][y2];
}
cout << f[n][n][n][n] << endl;
}