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

5 3 1 3 8 2 5 0 1 4 3 8 1 4 2 5 0 2 2 5 4 1 1

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;beginreadln(n,m);for i:=1 to n dobeginfor j:=1 to i doread(a[i,j]);readln;end;for i:=1 to n dofor j:=1 to i dof[i,j]:=max(f[i-1,j],f[i-1,j-1])+a[i,j];for i:=n downto 1 dofor j:=1 to i dog[i,j]:=max(g[i+1,j],g[i+1,j+1])+a[i,j];for i:=1 to n dobeginb[i,1]:=-1;b[i,2]:=-1;for j:=1 to i doif f[i,j]+g[i,j]-a[i,j]>b[i,1] thenbeginb[i,2]:=b[i,1];b[i,1]:=f[i,j]+g[i,j]-a[i,j];b[i,3]:=j;end elseif 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 dobeginreadln(x,y);if b[x,3]<>y then writeln(b[x,1]) else writeln(b[x,2]);end; end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9500044.html

總結

以上是生活随笔為你收集整理的2017年09月23日普级组 树塔狂想曲的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。