2.树塔
(tower)
【问题描述】
相信大家都在长训班学过树塔问题，题目很简单求最大化一个三角形数塔从上往下走的路径和。走的规则是：（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。
【输入输出样例】
|
tower.in |
tower.out |
|
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！
【数据规模和约定】
所有测试数据范围和特点如下：
对于所有数据，数塔中的数X的大小满足0≤X≤106
|
测试点编号 |
N |
M |
特殊约定 |
|
1 |
≤ 5 |
≤ 3 |
|
|
2 |
|
||
|
3 |
≤ 105 |
|
|
|
4 |
|
||
|
5 |
≤ 50 |
≤ 103 |
满足点(i,j)上的数=i*j |
|
6 |
|
||
|
7 |
|
||
|
8 |
|
||
|
9 |
≤ 300 |
≤ 104 |
数塔中所有数相等 |
|
10 |
|
||
|
11 |
|
||
|
12 |
|
||
|
13 |
≤ 1000 |
≤ 3*105 |
满足点(i,j)上的数=i-j |
|
14 |
满足点(i,j)上的数=i*j |
||
|
15 |
数塔中所有数相等 |
||
|
16 |
|
||
|
17 |
|
||
|
18 |
5*105 |
满足点(i,j)上的数=i-j |
|
|
19 |
|
||
|
20 |
|
这题我SB了，本应想到前后缀DP是可行的，但是我一直卡在去掉数字的影响导致65pt
考虑求出每一个位置从上到下的最大值和从小到大的最大值，枚举去掉的那一行的前后缀和的最大值就可以了
暴力其实可以拿80但是我分段分的不好
code：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 long long a[1005][1005],suf[1005][1005],pre[1005][1005]; 5 long long read(){ 6 long long x=0,f=1;char c=getchar(); 7 while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} 8 while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();} 9 return x*f; 10 } 11 int main() { 12 long long n,m; 13 n=read(),m=read(); 14 for(long long i=1; i<=n; i++) 15 for(long long j=1; j<=i; j++) 16 a[i][j]=read(),suf[i][j]=max(suf[i-1][j],suf[i-1][j-1])+a[i][j]; 17 for(long long i=n; i>=1; i--) 18 for(long long j=1; j<=i; j++) 19 pre[i][j]=max(pre[i+1][j],pre[i+1][j+1])+a[i][j]; 20 for(long long i=1; i<=m; i++) { 21 long long x=read(),y=read(),max0=0; 22 if(x==1&&y==1) {cout<<-1<<' ';continue;} 23 for(long long j=1; j<=x; j++) { 24 if(j==y)continue; 25 max0=max(max0,pre[x][j]+suf[x][j]-a[x][j]); 26 } 27 cout<<max0<<' '; 28 } 29 return 0; 30 }
over