数塔路径

题目链接：ybtoj高效进阶 21268

题目大意

给你一个三角形的数塔，然后多次询问，每次不准走一个点，问你从左上到右下的最长路径和是多少。
（只能向下或右下走）

思路

首先我们不难 DP 出最优答案，但它会 ban 点。

那我们考虑它 ban 掉的点会不会对最优答案造成影响，如果有影响，就找次优的。
（不一定是全局最优的，而是这一行选的不一样中最优的）

首先一行只会走一个点，那我们就可以求出最优的答案每一行走的点。
然后我们要看某一列选一个数的最大答案。

那我们就是从起点到它的最大值加它到终点的最大值减去它的权值。
（起点到它和它到终点可以 DP 求出）

然后就可以搞搞出来啦。

代码

#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

int n, m, a[1001][1001], pl[1001], x, y;
ll f[1002][1002], g[1002][1002];
ll maxn[1001], minn[1001];

ll clac(int x, int y) {
	return f[x][y] + g[x][y] - a[x][y];
}

int main() {
//	freopen("tower.in", "r", stdin);
//	freopen("tower.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			scanf("%d", &a[i][j]);
	
	for (int i = 1; i <= n; i++)//从起点到它的最长距离
		for (int j = 1; j <= i; j++)
			f[i][j] = a[i][j] + max((j == 1) ? 0 : f[i - 1][j - 1], (j == i) ? 0 : f[i - 1][j]);
	for (int i = n; i >= 1; i--)//从它到终点的最长
		for (int j = 1; j <= n; j++)
			g[i][j] = a[i][j] + max(g[i + 1][j], g[i + 1][j + 1]);
	
	for (int i = 1; i <= n; i++) {//最大答案和次大答案
		for (int j = 1; j <= i; j++) {
			if (clac(i, j) >= maxn[i]) {
				minn[i] = maxn[i]; maxn[i] = clac(i, j); pl[i] = j;//记得最大答案在这个 i 上的位置
			}
			else if (clac(i, j) >= minn[i]) minn[i] = clac(i, j);
		}
	}
	
	while (m--) {
		scanf("%d %d", &x, &y);
		if (x == 1 && y == 1) printf("-1\n");
			else if (y == pl[x]) printf("%lld\n", minn[x]);
				else printf("%lld\n", maxn[x]);
	}
	
	return 0;
}