2017年09月23日普级组树塔狂想曲

Description

相信大家都在长训班学过树塔问题，题目很简单求最大化一个三角形数塔从上往下走的路径和。走的规则是：（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掉一个点，而不是永久化的修改）。

Input

第一行包括两个正整数，N，M，分别表示数塔的高和询问次数。
以下N行，第i行包括用空格隔开的i - 1个数，描述一个高为N的数塔。
而后M行，每行包括两个数X，Y，表示第X行第Y列的数塔上的点被小S ban掉，无法通行。
（由于读入数据较大，c或c++请使用较为快速的读入方式）

Output

M行每行包括一个非负整数，表示在原图的基础上ban掉一个点后的最大路径和，如果被ban掉后不存在任意一条路径，则输出-1。

Sample Input

Sample Output

17
22
-1

Hint

【样例解释】

第一次是
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的大小满足
这里写图片描述

分析
对于每一个I 行j 列 I 和j不等于1 我们设f[i,j]为顶端往下走到I j这个位置的最大值，g[i,j]为从最下面一层走到位置（i，j）可以获得的最大值，那么经过位置（i，j）可以获得的分数就是f[i,j]+g[i,j]-a[i,j]。同时对于每一行我们找到一个最大值和一个次大值，并记录下它们的位置。对于输入的下，x，y （x，y为ban掉的数）我们判断是不是经过这一行的最大值的位置，若不是则输出次大值。（注意判断x=1）and （y=1）的情况。

程序：

uses math;
var
n,m,i,j,x,y:longint;
a,f,g:array[0..1001,0..1001]of longint;
b:array[0..1001,1..3]of longint;

begin
    readln(n,m);
    for i:=1 to n do
    begin
        for j:=1 to i do
        read(a[i,j]);
        readln;
    end;

    for i:=1 to n do
    for j:=1 to i do
    f[i,j]:=max(f[i-1,j],f[i-1,j-1])+a[i,j];

    for i:=n downto 1 do
    for j:=1 to i do
    g[i,j]:=max(g[i+1,j],g[i+1,j+1])+a[i,j];

    for i:=1 to n do
    begin
        b[i,1]:=-1;b[i,2]:=-1;
        for j:=1 to i do
        if f[i,j]+g[i,j]-a[i,j]>b[i,1] then
        begin
            b[i,2]:=b[i,1];
            b[i,1]:=f[i,j]+g[i,j]-a[i,j];
            b[i,3]:=j;
        end else
        if f[i,j]+g[i,j]-a[i,j]>b[i,2] then b[i,2]:=f[i,j]+g[i,j]-a[i,j];
    end;

    for i:=1 to m do
    begin
        readln(x,y);
        if b[x,3]<>y then writeln(b[x,1]) else writeln(b[x,2]);
    end;
end.

2017年09月23日普级组 树塔狂想曲

2017年09月23日普级组树塔狂想曲