题目大意
相信大家都在长训班学过树塔问题，题目很简单求最大化一个三角形数塔从上往下走的路径和。走的规则是：$(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掉一个点，而不是永久化的修改）。
题目分析
简单动规。
用$Up[i,j]$表示从$(1,1)$到达$(i,j)$的最大路径和，$Down[i,j]$表示从$(i,j)$到达$(n,i)$的最大路径和。
故我们可以使用$Up[i,j]+Down[i,j]-a[i,j]$表示经过$(i,j)$的最大路径和。
因为每行必须经过且只能经过一个结点，故每次ban掉一个结点，必定在该行另外新找一个结点使得权值和最大。
预处理行中$Up[i,j]+Down[i,j]-a[i,j]$的最大与次大，若ban掉最大则输出次大，否则输出最大。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1005;
int n,q,a[maxn][maxn],Up[maxn][maxn],Down[maxn][maxn],Max[maxn],Second[maxn];
int main() {
n=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++)
a[i][j]=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++)
Up[i][j]=max(Up[i-1][j-1],Up[i-1][j])+a[i][j];
for(int i=n; i>=1; i--)
for(int j=i; j>=1; j--)
Down[i][j]=max(Down[i+1][j],Down[i+1][j+1])+a[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++)
if(Up[i][j]+Down[i][j]-a[i][j]>Max[i]) {
Second[i]=Max[i];
Max[i]=Up[i][j]+Down[i][j]-a[i][j];
} else Second[i]=max(Second[i],Up[i][j]+Down[i][j]-a[i][j]);
for(int i=1; i<=q; i++) {
int x=Get_Int(),y=Get_Int();
if(x==1&&y==1)puts("-1");
else if(Up[x][y]+Down[x][y]-a[x][y]==Max[x])printf("%d\n",Second[x]);
else printf("%d\n",Max[x]);
}
return 0;
}
|
