题目描述
设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:
某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。
在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。
输入格式
第一行为一个整数N,表示 N×N 的方格图。
接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
行和列编号从 1 开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数,表示两条路径上取得的最大的和。
数据范围
N≤10
输入样例:
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
输出样例:
67
算法
(DP) $O(n^3)$
错解
从一条路径扩展到两条路径,这里不能使用贪心的思路,即先求第一条数字和最大的路径,再求出第二条;
因为如果第一条路径存在多种值,我们计算的时候只会取其中一条,可能会存在,选另一条路径作为第一条路径的解,此时第二条路径比我们计算时取得的第二条路径的和大
引用大佬的反例说明问题:
9 0 3
0 9 2
0 2 0
最长路径是9+9+2=209+9+2=20,假设这次走的路线是第一行的99、第二行的99和22,那么在第二次走的时候,地图变成
0 0 3
0 0 0
0 2 0
显然最长路径是33,总和为2323。
然而这不是最优解,最优解是第一次走第一行的99、第二行的99、第三行的22(仍是2020),但第二次可以走第一行的33、第二行的22,得到55,总和达到2525。
正解
AcWing 1015.摘花生中只需要求一条路径,而本题需要求两条路径;
AcWing 1015.摘花生中的状态表示为:f[x1][y1],即从(1,1)走到(x1, y1)路径和的最大值;
由此受到启发,本题的状态表示为f[x1][y1][x2][y2],
含义为分别从(1,1)(1,1)出发走到终点(x1, y1)(x2, y2)两条路径和的最大值
由于两条路径同时出发,每次各走一步,所以x1 + y1 == x2 + y2, 所以可以优化掉一维,
另状态表示为f[k][x1][x2],此时y1 = k - x1, y2 = k - x2, 含义与四维状态表示相同;
状态转移如何表示?
因为第一条路径和第二条路径各走一步并且互相独立(后面会处理两个路径走到相同格子的取值), 并且每条路径可以由两个方向转移过来,
所以总的转移分为四个情况:
1. (x1 - 1, y1) (x2 - 1, y2) -> (x1, y1) (x2, y2)
2. (x1 - 1, y1) (x2, y2 - 1) -> (x1, y1) (x2, y2)
3. (x1, y1 - 1) (x2 - 1, y2) -> (x1, y1) (x2, y2)
4. (x1, y1 - 1) (x2, y2 - 1) -> (x1, y1) (x2, y2)
对应到状态转移方程即:
f[k][x1][x2] = max(max(f[k - 1][x1 - 1][x2 - 1], f[k - 1][x1 - 1][x2]), max(f[k - 1][x1][x2 - 1], f[k - 1][x1][x2]));
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n;
int w[N][N];
int f[2*N][N][N];
int get(int k, int x1, int x2){
return max(max(f[k - 1][x1 - 1][x2 - 1], f[k - 1][x1][x2]), max(f[k - 1][x1 - 1][x2], f[k - 1][x1][x2 - 1]));
}
int main(){
cin >> n;
int x, y, a;
while(cin >> x >> y >> a, x || y || a) w[x][y] = a;
for(int k = 2; k <= 2 * n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
int y1 = k - i, y2 = k - j;
if(y1 < 1 || y1 > n || y2 < 1 || y2 > n) continue;
f[k][i][j] = get(k, i, j) + w[i][y1];
if(i != j) f[k][i][j] += w[j][y2];
}
}
}
cout << f[2*n][n][n] << endl;
return 0;
}