分析题可以得出如下结论:
-
结论1:不能用局部贪心做,这道题局部贪心无法推出全局贪心的正确性
-
结论2:假设存在两条路有交叉的情况,由于本题要求的是和最大,因此可以调整两条路线使其不交叉,而并不影响最终结果,此时两条路线处于一上一下的关系:
基于以上两点,我们可以让两条路线让两个人来走,同时出发,步调一致,这样一旦两人路线有交叉的趋势,则执行结论2的操作(即一个人始终在另一个人上方),同时碰面点的数记得取走。
因此可以用3维状态方程来表示,f[k] [i] [j]表示走了(横纵坐标和为k)这么多步,此时第一个人纵坐标i,第二个人纵坐标j情况下的所有路线的集合。始终保持i>=j即可(即第一个人始终在第二个人上方)。
状态转移方程:f[k] [i] [j] = max(f[k-1] [i-1] [j-1], f[k-1] [i] [j], f[k-1] [i-1] [j], f[k-1] [i] [j-1]),前提是i >=j。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] a = new int[n+1][n+1];
int[][][] f = new int[2*n+1][n+1][n+1]; //横纵坐标和最大为2*n
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
while(x != 0 || y != 0 || z != 0) {
a[x][y] = z;
x = sc.nextInt();
y = sc.nextInt();
z = sc.nextInt();
}
f[2][1][1] = a[1][1];
for(int k = 3; k <= 2*n; k++)
for(int i = 1; i <= n && i+1 <= k; i++) { //条件x:i+1(最小的横坐标为1)不能比k还大
if(k-i > n) continue; //第一个人的纵坐标要 <=n
for(int j = 1; j <= i; j++) {
if(k-j > n) continue; //第二个人的纵坐标要 <=n
//f[k] [i] [j] = max(f[k-1] [i-1] [j-1], f[k-1] [i] [j], f[k-1] [i-1] [j], f[k-1] [i] [j-1])
f[k][i][j] = f[k-1][i-1][j-1];
if(i+1 <= k-1) { //f[k-1][i][j] 需要满足条件x
f[k][i][j] = Math.max(f[k][i][j], f[k-1][i][j]);
f[k][i][j] = Math.max(f[k][i][j], f[k-1][i][j-1]);
}
if(i-1>=j) //不能交叉
f[k][i][j] = Math.max(f[k][i][j], f[k-1][i-1][j]);
if(i == j)
f[k][i][j] += a[k-i][i];
else
f[k][i][j] += a[k-i][i] + a[k-j][j];
}
}
System.out.println(f[2*n][n][n]);
}
}