题目
相信大家都学过树塔问题，题目很简单求最大化一个三角形数塔从上往下走的路径和。走的规则是：（i，j） 号点只能走向 （i+1，j） 或者 （i+1，j+1）。如下图是一个数塔，映射到该数塔上行走的规则为：从左上角的点开始，向下走或向右下走直到最底层结束。
1
3 8
2 5 0
1 4 3 8
1 4 2 5 0
路径最大和是 1+8+5+4+4=22，1+8+5+3+5=22 或者 1+8+0+8+5=22。
小 SS 觉得这个问题 so easy。于是他提高了点难度，他每次 ban 掉一个点（即规定哪个点不能经过），然后询问你不走该点的最大路径和。当然他上一个询问被 banban 掉的点过一个询问会恢复（即每次他在原图的基础上 ban 掉一个点，而不是永久化的修改）。
输入
第一行包括两个正整数 N,M 分别表示数塔的高和询问次数。
以下 N 行，第 ii 行包括用空格隔开的 i−1 个数，描述一个高为 N 的数塔。
而后 M 行，每行包括两个数 X,Y，表示第 X 行第 Y 列的数塔上的点被小 S ban 掉，无法通行。
（由于读入数据较大，请使用较为快速的读入方式）
输出
M 行每行包括一个非负整数，表示在原图的基础上 ban 掉一个点后的最大路径和，如果被 ban 掉后不存在任意一条路径，则输出 −1。
样例输入
5 3
1
3 8
2 5 0
1 4 3 8
1 4 2 5 0
2 2
5 4
1 1
样例输出
17
22
-1
样例说明
第一次：
1
3 X
2 5 0
1 4 3 8
1 4 2 5 0
1+3+5+4+4 = 17 或者 1+3+5+3+5=17
第二次：
1
3 8
2 5 0
1 4 3 8
1 4 2 X 0
1+8+5+4+4 = 22
第三次：无法通行，-1！
数据规模与约定
时间限制：1 s
内存限制：256 M
100% 的数据保证 1≤N≤1000,1≤M≤5∗1051≤N≤1000,1≤M≤5∗105
思路
- 动态规划 ：从上往下求 ，再从下往上求，并将结果保留在两个数组中
- 对于每个点（x, y）能知道经过它的最大路径和 xs[x] [y] + sx[x] [y] - num[x] [y];
- 遍历每一行，将每一行最大值、次大值的 列坐标保存
- 输入数据 ，若该ban的点为经过最大值的点，则输出该行次大值，否则正常输出最大值ans[1] [1], 并注意特判-1；
代码演示
#include <stdio.h>
long long num[1025][1025], ans[1025][1025], xs[1025][1025], sx[1025][1025], first[1025], second[1025];
#define max(a, b) ({ \
__typeof(a) _a = (a); \
__typeof(b) _b = (b); \
_a > _b ? _a : _b; \
})
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%lld", &num[i][j]);
}
}
/*
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
*/
//从上往下
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
sx[i][j] = num[i][j] + max(sx[i - 1][j], sx[i - 1][j - 1]);
}
}
//从下往上
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
xs[i][j] = max(xs[i + 1][j], xs[i + 1][j + 1]) + num[i][j];
}
}
for (int i = 1; i <= n; i++) {
int f = 0, s = 0, s_ind = 0, f_ind = 0;
for (int j = 1; j <= i; j++) {
ans[i][j] = xs[i][j] + sx[i][j] - num[i][j];
// printf("%lld ", ans[i][j]);
if (f < ans[i][j]) {
s_ind = f_ind;
s = f;
f = ans[i][j];
f_ind = j;
} else if (ans[i][j] > s) {
s = ans[i][j];
s_ind = j;
}
first[i] = f_ind, second[i] = s_ind; //记录每一行最大值、次大值列坐标
}
// printf("\n");
}
//for (int i = 1; i <= n; i++) printf("%lld %lld\n", first[i], second[i]);
while (m--) {
int a, b;
scanf("%d %d", &a, &b);
if (a == 1) { //特判-1；
printf("-1\n");
} else if (first[a] == b) { //最大值被ban了
printf("%lld\n", ans[a][second[a]]); //输出次大值
} else printf("%lld\n", ans[1][1]); //输出最大值
}
return 0;
}
