题目
设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:
某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。
在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。
输入格式
第一行为一个整数N,表示 N×N 的方格图。
接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
行和列编号从 开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数,表示两条路径上取得的最大的和。
数据范围
输入样例:
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
解题
方法一:动态规划 数字三角形模型
错误思路
为什么不能先走第一次求出最大值并记录最优路径,然后把路径上的点清零后再走第二次最优路线?
因为:第一次走虽然为局部最优但是对第二次走造成了影响,这就导致第二次走是在第一次影响下所能走的局部最优,不具备「无后效性」,因此分开两次走并不是全局最优解。
例如:
0 1 0
2 2 2
1 0 0
这样的测试用例,在第一次走时一定会把所有的 都拿完以得到最优路径,第二次走就只能拿到一个 了。
而第一次走不追求局部最优解是可以把图中所有数给拿完的。
错误代码
import java.util.*;
import java.io.*;
public class Main {
static final int N = 15;
static int[][] g = new int[N][N], f = new int[N][N];
static boolean[][] prevs = new boolean[N][N];
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
while (true) {
in.nextToken();
int i = (int) in.nval;
if (i == 0) break;
in.nextToken();
int j = (int) in.nval;
in.nextToken();
int x = (int) in.nval;
g[i][j] = x;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (f[i - 1][j] > f[i][j - 1]) {
f[i][j] = f[i - 1][j] + g[i][j];
prevs[i][j] = true;
} else f[i][j] = f[i][j - 1] + g[i][j];
}
}
int ans = f[n][n];
for (int i = n, j = n; i > 0 && j > 0;) {
g[i][j] = 0;
if (prevs[i][j]) --i;
else --j;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]) + g[i][j];
}
}
System.out.println(ans + f[n][n]);
}
}
正确思路
在只走一次的题目的基础上延伸,首先考虑用 表示所有第一次从 走到 ,第二次从 走到 的所有路径中取得数字和的最大值。
在上面的错误思路中我们发现不能分开考虑两次走的路径,所以尝试两次一起走,那么就需要在求最优路径的基础上同时判断「同一个格子不能被重复选择」极了。
由于每次只能向下或向右行走,不能回头,那么只有在两次走到同一步时才有机会选择到同一个格子,也就是说只有在 时,两条路径选择的格子才有可能重合,因此可以把路径长度作为 DP 的阶段,每个阶段中,我们同时把两条路径扩展一步(即路径长度加 ),来进入下一个阶段。
综上所述,使用 表示所有第一次从 走到 ,第二次从 走到 的所有路径中取得数字和的最大值,其中 。
于是,动态规划的初始状态为: ,目标状态为: 。
对于如何判断两次路径选择了同一个方格,由于每个阶段两条路线所选点的横纵坐标和相同,若横坐标相同,则纵坐标必相同,故使用 来判断:
- 时,两路线选格相同,只取一次 即可。
- 时,两路线选格不同, 与 都要取到。
总结:
-
状态定义: 表示所有第一次从 走到 ,第二次从 走到 的所有路径中取得数字和的最大值。
-
状态转移方程:
-
初始状态: 。
代码
import java.util.*;
import java.io.*;
public class Main {
static final int N = 15;
static int[][] g = new int[N][N];
static int[][][] f = new int[N * 2][N][N];
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
while (true) {
in.nextToken();
int i = (int) in.nval;
if (i == 0) break;
in.nextToken();
int j = (int) in.nval;
in.nextToken();
int x = (int) in.nval;
g[i][j] = x;
}
for (int k = 2; k <= n + n; ++k) {
for (int i1 = 1; i1 <= n; ++i1) {
for (int i2 = 1; i2 <= n; ++i2) {
int j1 = k - i1, j2 = k - i2;
if (j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue;
int t = g[i1][j1];
if (i1 != i2) t += g[i2][j2];
f[k][i1][i2] = Math.max(Math.max(f[k - 1][i1 - 1][i2 - 1], f[k - 1][i1][i2]),
Math.max(f[k - 1][i1][i2 - 1], f[k - 1][i1 - 1][i2])) + t;
}
}
}
System.out.println(f[n * 2][n][n]);
}
}
评论区