相信大家都在长训班学过树塔问题，题目很简单求最大化一个三角形数塔从上往下走的路径和。走的规则是：（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。 小S觉得这个问题so easy。于是他提高了点难度，他每次ban掉一个点（即规定哪个点不能经过），然后询问你不走该点的最大路径和。 当然他上一个询问被ban掉的点过一个询问会恢复（即每次他在原图的基础上ban掉一个点，而不是永久化的修改）。
第一行包括两个正整数，N，M，分别表示数塔的高和询问次数。 以下N行，第i行包括用空格隔开的i - 1个数，描述一个高为N的数塔。 而后M行，每行包括两个数X，Y，表示第X行第Y列的数塔上的点被小S ban掉，无法通行。 （由于读入数据较大，c或c++请使用较为快速的读入方式）
M行每行包括一个非负整数，表示在原图的基础上ban掉一个点后的最大路径和，如果被ban掉后不存在任意一条路径，则输出-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！
数据非常大 所以不能读一次搜一次 详细思路见代码
#include<Algorithm> #include<Iostream> #include<Cstring> #include<Cstdio> using namespace std; int A[2250][2250],F[2250][2]; int Ans_x[2250][2250],Ans_y[2250][2250]; int Ans,n,m,x,y; int read() //快读 { int z=0,flag=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();} while(ch>='0'&&ch<='9'){z=z*10+ch-'0';ch=getchar();} return z*flag; } void write(int k)//快输 {if(k)write(k/10),putchar(k%10+48);} int main() { n=read();m=read(); for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) { A[i][j]=read(); Ans_x[i][j]=A[i][j]+max(Ans_x[i-1][j],Ans_x[i-1][j-1]);//计算顺推的答案 } for(int i=n;i>=1;--i) for(int j=1;j<=i;++j) Ans_y[i][j]=A[i][j]+max(Ans_y[i+1][j],Ans_y[i+1][j+1]);//计算逆推的答案 for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) { //F[i][0]代表第i行第一大的答案，[1]表示次大的答案 if(Ans_x[i][j]+Ans_y[i][j]-A[i][j]>F[i][0])//计算时会有重复，所有减去本身 F[i][1]=F[i][0],F[i][0]=Ans_x[i][j]+Ans_y[i][j]-A[i][j]; else F[i][1]=max(F[i][1],Ans_x[i][j]+Ans_y[i][j]-A[i][j]); } for(int k=1;k<=m;++k) { x=read();y=read(); if(x==1 && y==1){printf("-1\n");continue;} if(Ans_x[x][y]+Ans_y[x][y]-A[x][y]!=F[x][0])write(F[x][0]),putchar(10);//如果不相同 else write(F[x][1]),putchar(10); } return 0; }