動態規劃經典教程
引言：本人在做過一些題目後對 DP 有些感想，就寫了這個總結：
第一節 動態規劃基本概念
一，動態規劃三要素：階段，狀態，決策。
他們的概唸到處都是，我就不多說了，我只說說我對他們的理解：
如果把動態規劃的求解過程看成一個工廠的生產線，階段就是生產某個商品的不同的環節，狀態就是工件當前的形態，決策就是對工件的操作。顯然不同階段是對產品的一個前面各個狀態的小結，有一個個的小結構成了最終的整個生產線。每個狀態間又有關聯（下一個狀態是由上一個狀態做了某個決策後產生的）。
下面舉個例子：
要生產一批雪糕，在這個過程中要分好多環節：購買牛奶，對牛奶提純處理，放入工廠加工，加工後的商品要包裝，包裝後就去銷售……，這樣沒個環節就可以看做是一個階段；產品在不同的時候有不同的狀態，剛開始時只是白白的牛奶，進入生產後做成了各種造型，從冷凍庫拿出來後就變成雪糕（由液態變成固態 =_=||）。每個形態就是一個狀態，那從液態變成固態經過了冰凍這一操作，這個操作就是一個決策。
一個狀態經過一個決策變成了另外一個狀態，這個過程就是狀態轉移，用來描述狀態轉移的方程就是狀態轉移方程。
經過這個例子相信大家對動態規劃有所瞭解了吧。
下面在說說我對動態規劃的另外一個理解：
用圖論知識理解動態規劃：把動態規劃中的狀態抽象成一個點，在有直接關聯的狀態間連一條有向邊，狀態轉移的代價就是邊上的權。這樣就形成了一個有向無環圖 AOE 網（為什麼無環呢？往下看）。對這個圖進行拓撲排序，刪除一個邊後同時出現入度為 0 的狀態在同一階段。這樣對圖求最優路徑就是動態規劃問題的求解。
二，動態規劃的適用範圍
動態規劃用於解決多階段決策最優化問題，但是不是所有的最優化問題都可以用動態規劃解答呢？
一般在題目中出現求最優解的問題就要考慮動態規劃了，但是否可以用還要滿足兩個條件：
最優子結構（最優化原理）
無後效性
最優化原理在下面的最短路徑問題中有詳細的解答；
什麼是無後效性呢？
就是說在狀態 i 求解時用到狀態 j 而狀態 j 就解有用到狀態 k….. 狀態 N。
而求狀態 N 時有用到了狀態 i 這樣求解狀態的過程形成了環就沒法用動態規劃解答了，這也是上面用圖論理解動態規劃中形成的圖無環的原因。
也就是說當前狀態是前面狀態的完美總結，現在與過去無關。。。
當然，有是換一個劃分狀態或階段的方法就滿足無後效性了，這樣的問題仍然可以用動態規劃解。
三，動態規劃解決問題的一般思路。
拿到多階段決策最優化問題後，第一步要判斷這個問題是否可以用動態規劃解決，如果不能就要考慮搜索或貪心了。當卻定問題可以用動態規劃後，就要用下面介紹的方法解決問題了：
（1）模型匹配法：
最先考慮的就是這個方法了。挖掘問題的本質，如果發現問題是自己熟悉的某個基本的模型，就直接套用，但要小心其中的一些小的變動，現在考題辦都是基本模型的變形套用時要小心條件，三思而後行。這些基本模型在先面的分類中將一一介紹。
（2）三要素法
仔細分析問題嘗試著確定動態規劃的三要素，不同問題的卻定方向不同：
先確定階段的問題：數塔問題，和走路問題（詳見解題報告）
先確定狀態的問題：大多數都是先確定狀態的。
先確定決策的問題：背包問題。（詳見解題報告）
一般都是先從比較明顯的地方入手，至於怎麼知道哪個明顯就是經驗問題了，多做題就會發現。
（3）尋找規律法：
這個方法很簡單，耐心推幾組數據後，看他們的規律，總結規律間的共性，有點貪心的意思。
（4）邊界條件法
找到問題的邊界條件，然後考慮邊界條件與它的領接狀態之間的關係。這個方法也很起效。
（5）放寬約束和增加約束
這個思想是在陳啟鋒的論文裡看到的，具體內容就是給問題增加一些條件或刪除一些條件使問題變的清晰。
第二節 動態規劃分類討論
這裡用狀態維數對動態規劃進行了分類：
1. 狀態是一維的
1．1 下降 / 非降子序列問題：
問題描述： {挖掘題目的本質，一但抽象成這樣的描述就可以用這個方法解}
在一個無序的序列 a1,a2,a3,a4…an 裡，找到一個最長的序列滿足：ai<=aj<=ak…<=am, 且 i<j<k…aj>ak…>am, 且 i>j>k…>m.（最長下降子序列）。
問題分析：
如果前 i-1 個數中用到 ak (ak>ai 或 akai (或 aj<=ai)，opt [j]+1 就是 opt [i] 的值；用方程表示為：{我習慣了這種寫法，但不是狀態轉移方程的標準寫法 }
opt [i]=max (opt [j])+1 (0<=j<i 且 aj<=ai) {最長非降子序列}
opt [i]=max (opt [j])+1 (0<=j_ai) {最長下降子序列}
實現求解的部分代碼：
opt [0]:=maxsize；{maxsize 為 maxlongint 或 - maxlongint}
for i:=1 to n do
for j:=0 to i-1 do
if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if opt [i]>ans then ans:=opt [i]; {ans 為最終解}
複雜度：從上面的實現不難看出時間複雜度為 O（N2），空間複雜度 O（N）；_
例題 1 攔截導彈 (missile.pas/c/cpp) 來源：NOIP1999 (提高組) 第一題
【問題描述】
某國為了防禦敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發砲彈能夠到達任意的高度，但是以後每一發砲彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈依次飛來的高度（雷達給出的高度數據是不大於 30000 的正整數），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。
【輸入文件】missile.in
單獨一行列出導彈依次飛來的高度。
【輸出文件】missile.out
兩行，分別是最多能攔截的導彈數，要攔截所有導彈最少要配備的系統數
【輸入樣例】
389 207 155 300 299 170 158 65
【輸出樣例】
6
2
【問題分析】
有經驗的選手不難看出這是一個求最長非升子序列問題，顯然標準算法是動態規劃。
以導彈依次飛來的順序為階段，設計狀態 opt [i] 表示前 i 個導彈中攔截了導彈 i 可以攔截最多能攔截到的導彈的個數。
狀態轉移方程：
opt[i]=max(opt[j])+1 (h[i]>=h[j],0=<j_=a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
anslen:=0;
for i:=1 to n do
if opt[i]>anslen then
anslen:=opt[i];
fillchar(opt,sizeof(opt),0);
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]opt[i]) then
opt[i]:=opt[j]+1;
anstime:=0;
for i:=1 to n do
if opt[i]>anstime then
anstime:=opt[i];
end;
procedure print;
begin
writeln(anslen);
writeln(anstime);
close(input);
close(output);
end;
begin
init;
main;
print;
end._
例題二 合唱隊形 (chorus.pas/c/cpp) 來源：NOIP2004 (提高組) 第一題
N 位同學站成一排，音樂老師要請其中的 (N-K) 位同學出列，使得剩下的 K 位同學排成合唱隊形。
合唱隊形是指這樣的一種隊形：設 K 位同學從左到右依次編號為 1，2…，K，他們的身高分別為 T1，T2，…，TK， 則他們的身高滿足 T1<...Ti+1>…>TK (1<=i<=K)。
你的任務是，已知所有 N 位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。
【輸入文件】
輸入文件 chorus.in 的第一行是一個整數 N (2<=N<=100)，表示同學的總數。第一行有 n 個整數，用空格分隔，第 i 個整數 Ti (130<=Ti<=230) 是第 i 位同學的身高 (釐米)。
【輸出文件】
輸出文件 chorus.out 包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。
【樣例輸入】
8
186 186 150 200 160 130 197 220
【樣例輸出】
4
【數據規模】
對於 50％的數據，保證有 n<=20；
對於全部的數據，保證有 n<=100。
【問題分析】
出列人數最少，也就是說留的人最多，也就是序列最長。
這樣分析就是典型的最長下降子序列問題。只要枚舉每一個人站中間時可以的到的最優解。顯然它就等於，包括他在內向左求最長上升子序列，向右求最長下降子序列。
我們看一下複雜度：
計算最長下降子序列的複雜度是 O（N2），一共求 N 次，總複雜度是 O（N3）。這樣的複雜度對於這個題的數據範圍來說是可以 AC 的。但有沒有更好的方法呢？
其實最長子序列只要一次就可以了。因為最長下降（上升）子序列不受中間人的影響。
只要用 OPT1 求一次最長上升子序列，OPT2 求一次最長下降子序列。這樣答案就是 N-max (opt1 [i]+opt2 [i]-1).
複雜度由 O（N3）降到了 O（N2）。
【源代碼】
program chorus;
const
fin='chorus.in';
fout='chorus.out';
maxn=200;
var
opt1,opt2,a[0..maxn] of longint;
n,ans;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j;
begin
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]opt1[i]) then
opt1[i]:=opt1[j]+1;
a[n+1]:=-maxlongint;
for i:=n downto 1 do
for j:=i+1 to n+1 do
if (a[j]opt2[i]) then
opt2[i]:=opt2[j]+1;
ans:=0;
for i:=1 to n do
if opt1[i]+opt2[i]>ans then
ans:=opt1[i]+opt2[i];
end;
procedure print;
begin
writeln(n-ans+1);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題 3 Buy Low Buy Lower (buylow.pas/c/cpp) 來源: USACO 4-3-1
【問題描述】
「逢低吸納」是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:
"逢低吸納，越低越買"
這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低。按照這個規則購買股票的次數越多越好，看看你最多能按這個規則買幾次。
給定連續的 N 天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。
以下面這個表為例，某幾天的股價是:
天數 1 2 3 4 5 6 7 8 9 10 11 12
股價 68 69 54 64 68 64 70 67 78 62 98 87
這個例子中，聰明的投資者 (按上面的定義)，如果每次買股票時的股價都比上一次買時低，那麼他最多能買 4 次股票。一種買法如下 (可能有其他的買法):
天數 2 5 6 10
股價 69 68 64 62
【輸入文件】buylow.in
第 1 行: N (1 <= N =a [j],0=<j<i) {a [i] 存第 i 天股價}
最大的 opt [i] 就是最終的解。
第二問呢，稍麻煩一點。
從問題的邊界出發考慮問題，當第一問求得一個最優解 opt [i]=X 時，
在 1 到 N 中如果還有另外一個 opt [j]=x 那麼選取 J 的這個方案肯定是成立的。
是不是統計所有的 opt [j]=x 的個數就是解了呢？
顯然沒那麼簡單，因為選取Ｊ這天的股票構成的方案不見得＝１，看下面一個例子：
５ 6 4 3 １ 2
方案一：５４３１
方案二：５４３２
方案三：６４３１
方案四：６４３２
x=4
也就是所雖然 opt [5]=X 和 opt [6]=X 但個數隻有兩個，而實際上應該有四個方案，但在仔細觀察發現，構成 opt [5]=x 的這個方案中 opt [j]=x-1 的方案數有兩個，opt [j]=x-2 的有一個，opt [j]=x-3 的有一個……
顯然這是滿足低歸定義的設計函數 F（i）表示前 I 張中用到第 i 張股票的方案數。
遞推式：
1 (i=0)
F(i)=
Sum (F (j)) (0<=ja [i],opt [j]=opt [i]-1) {sum 代表求和}
答案 = sum (F (j)) {0<ja [i]) and (opt [j]+1>opt [i]) then
opt[i]:=opt[j]+1;
for i:=1 to n do
begin
j:=i-1;
while (j>0) and ((opt[i]opt[j]) or (a[i]a[j])) do
dec(j);
next[i]:=j;
end;
F[0,1]:=1;
for i:=1 to n+1 do
for j:=i-1 downto next[i] do
if (opt[j]=opt[i]-1) and (a[j]>a[i]) then
Hinc(F[i],F[j]);
end;
procedure print;
var
i,top,m;
begin
write(opt[n+1]-1,' ');
top:=maxsize;
while (top>1) and (F[n+1][top]=0) do
dec(top);
write(F[n+1,top]);
for i:=top-1 downto 1 do
begin
m:=F[n+1,i];
while m<maxsize div 10 do
begin
write('0');
m:=m*10;
end;
write(F[n+1,i]);
end;
writeln;
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題 4 船 (ships.pas/c/cpp) 來源：《奧賽經典》（提高篇）
【問題描述】
PALMIA 國家被一條河流分成南北兩岸，南北兩岸上各有 N 個村莊。北岸的每一個村莊有一個唯一的朋友在南岸，且他們的朋友村莊彼此不同。
每一對朋友村莊想要一條船來連接他們，他們向政府提出申請以獲得批准。由於河面上常常有霧，政府決定禁止船隻航線相交（如果相交，則很可能導致碰船）。
你的任務是編寫一個程序，幫助政府官員決定批准哪些船隻航線，使得不相交的航線數目最大。
【輸入文件】ships.in
輸入文件由幾組數據組成。每組數據的第一行有 2 個整數 X，Y，中間有一個空格隔開，X 代表 PALMIA 河的長度（10<=X<=6000），Y 代表河的寬度（10<=Y<=100）。第二行包含整數 N，表示分別坐落在南北兩岸上的村莊的數目（1<=N<=5000）。在接下來的 N 行中，每一行有兩個非負整數 C，D，由一個空格隔開，分別表示這一對朋友村莊沿河岸與 PALMIA 河最西邊界的距離（C 代表北岸的村莊，D 代表南岸的村莊），不存在同岸又同位置的村莊。最後一組數據的下面僅有一行，是兩個 0，也被一空格隔開。
【輸出文件】ships.out
對輸入文件的每一組數據，輸出文件應在連續的行中表示出最大可能滿足上述條件的航線的數目。
【輸入樣例】
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0
【輸出樣例】
4
【問題分析】
這道題目相對來說思考難度較高，從字面意義上看不出問題的本質來，有點無法下手的感覺。這裡我給大家推薦兩種思考這類問題的方法。
法一：尋找規律法（我前面總結提到的第 3 個方法）
尋找規律自然要推幾組數據，首先當然有從樣例入手；
仔細觀察上圖：紅色航線是合法的，那麼他們滿足什麼規律呢？
C1 C2 C3 C4
北岸紅線的端點： 4 9 15 17
南岸紅線的端點： 2 8 12 17
D1 D2 D3 D4
不難看出無論線的斜率如何，都有這樣的規律：
C1<C2<C3<C4 且 D1<D2<D3<D4
如果我們把輸入數據排升序，問題變抽象為：
在一個序列（D）裡找到最長的序列滿足 DI<DJ<Dk…… 且 i<j<k
這樣的話便是典型的最長非降子序列問題了。。。。
法二：邊界條件法（我前面總結提到的第 4 個方法）
邊界法其實就是把數據往小了縮，顯然 N=1 是答案是 1。N=2 時呢？
考慮這樣一組數據：
N=2
C1 D1
C2 D2
當 C1D2 那麼一定會相交，反之則不會相交。
當 C1 >C2 時，如果 D1<D2 那麼一定會相交，反之則不會相交。
N=3
C1 D1
C2 D2
C3 D3
……
其實不用在推導 N=3 了，有興趣的可以推導去。看 N=2 時就能得出：
對於任意兩條航線如果滿足 Ci<Cj 且 Di<Dj 則兩條航線不相交。這樣的話要想在一個序列裡讓所有的航線都不相交那比然滿足，C1<C2<C3…Cans 且 D1<D2<D3…<Dans ，也就是將 C 排序後求出最長的滿足這個條件的序列的長度就是解。
這樣分析後顯然是一個最長非降子序列問題。
複雜度：排序可以用 O（nlogn）的算法，求最長非降子序列時間複雜度是 O (n2).
總複雜度為 O（n2）.
【源代碼】
program ships;
const
fin='ships.in';
fout='ships.out';
maxn=5010;
type
retype=record
C,D;
end;
var
x,y,n,ans;
a[0..maxn] of retype;
opt[0..maxn] of longint;
procedure init;
var
i;
begin
readln(n);
for i:=1 to n do
read(a[i].c,a[i].d);
end;
procedure quick(L,r);
var
i,j,x;
y;
begin
i:=L;
j:=r;
x:=a[(i+j) div 2].c;
repeat
while a[i].cx do
dec(j);
if ij;
if j>L then quick(L,j);
if i<r then quick(i,r);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
quick(1,n);
for i:=1 to n do
for j:=0 to i-1 do
if (a[j].dopt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if ans<opt[i] then
ans:=opt[i];
writeln(ans);
end;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(x,y);
while (x+y0) do
begin
init;
main;
read(x,y);
end;
close(input);
close(output);
end.
1.2 背包問題
首先說說背包問題的基本模型：
現有 N 個物品，每個物品的價值為 V，重量為 W。求用一個載重量為 S 的背包裝這寫物品，使得所裝物品的總價值最高。
背包問題用貪心和搜索解，當然效果不佳，不過在我的貪心和搜索總結中會說到。顯然標準的解法是動態規化，我在解決這個問題時習慣設計一維狀態，還可以設計二維的，二維狀態在下面會講，現在只討論用一維狀態實現背包問題。
背包問題的分類：
(1) 小數背包：物品的重量是實數，如油，水等可以取 1.67 升……
(2) 整數背包：0/1 背包：每個物品只能選一次，或不選。不能只選一部分
部分背包：所選物品可以是一部分。
(3) 多重背包：背包不只一個。
小數背包：在貪心總結中會細講。
整數背包：
部分背包：同小數背包。
0/1 背包：這個問題是最經常出現的問題，應該熟練掌握。
我們先看一下 0/1 背包的簡化版：
現有 N 個物品，每個物品重量為 W，這些物品能否使在載重量為 S 的背包裝滿（即重量和正好為 S）？如過不能那能使物品重量和最重達到多少？
針對這一問題我們以物品的個數分階段，設計一個狀態 opt [i] 表示載重量為 i 的背包可否裝滿，顯然 opt [i] 的基類型是 boolean。
決策是什麼呢？
當要裝第 i 個物品時，如果前 i-1 個物品可以使載重為 k 的背包裝滿，那麼載重為 k+w [i] 的背包就可以裝滿。於是對於一個 opt [j] 來說，只要 opt [j-w [i]] 是 true（表示可裝滿）那 opt [j] 就可以裝滿，但要注意：針對每一個物品枚舉背包的載重量時如果這樣正向的推導會使同一個物品用好幾次，因為 k+w [i] 可裝滿那 k+w [i]+w [i] 就可裝滿，但實際上是裝不滿的因為物品只有一個。解決這個問題很簡單，只要逆向推導就 OK 了。
這樣劃分階段，設計狀態，滿足無後效性和麼？
顯然對與一個每一個階段都是獨立的，物品的順序並不影響求解，因為裝物品的次序不限。而對於 opt [j] 只考慮 opt [j-w [i]] 而不考慮後面的，所以滿足無後效性。
有了上面的分析不難寫出狀態轉移方程：
opt[j]:=opt[j-w[1]] {opt[j-w[i]]=true}
時間複雜度：
階段數 O (S)* 狀態數（O (N)）* 轉移代價（O (1)）=O（SN）
下面看幾個例題：
例題 5 裝箱問題 (pack.pas/c/cpp) 來源：NOIP2001 (普及組) 第四題
【問題描述】
有一個箱子容量為 V（正整數，0＜＝V＜＝20000），同時有 n 個物品（0＜n＜＝30＝，每個物品有一個體積（正整數）。
要求 n 個物品中，任取若干個裝入箱內，使箱子的剩餘空間為最小。
【輸入文件】
第一 行一個正整數 V 表示箱子的容量，第二行一個正整數 N 表示物品個數，接下來 N 行列出這 N 個物品各自的體積。
【輸出文件】
單獨一行，表示箱子最小的剩餘空間。
【輸入樣例】
24
6
8
3
12
7
9
7
【輸出樣例】
0
【問題分析】
本題是經典的 0/1 背包問題，並且是 0/1 背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩餘空間最小也就是儘量裝滿背包。於是這個問題便成了：
有一個栽重量為 V 的背包，有 N 個物品，儘量多裝物品，使背包儘量的重。
設計一個狀態 opt [i] 表示重量 i 可否構成。
狀態轉移方程：opt [j]:=opt [j-w [1]] {opt [j-w [i]]=true}
最終的解就是 v-x（x<=n 且 opt [x]=true 且 opt [x+1..n]=false）。
【源代碼 1】
program pack;
const
fin='pack.in';
fout='pack.out';
maxv=20010;
maxn=100;
var
opt[0..maxv] of boolean;
w[0..maxn] of longint;
v,n,x;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(v);
read(n);
for i:=1 to n do
read(w[i]);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to n do
for j:=v downto w[i] do
if opt[j-w[i]] then opt[j] :=true;
x:=v;
while not opt[x] do dec(x);
end;
procedure print;
begin
writeln(v-x);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題 6 砝碼稱重 來源：NOIP1996（提高組） 第四題
【問題描述】
設有 1g、2g、3g、5g、10g、20g 的砝碼各若干枚（其總重 <=1000），用他們能稱出的重量的種類數。
【輸入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝碼有 a1 個，2g 砝碼有 a2 個，…，20g 砝碼有 a6 個，中間有空格）。
【輸出文件】
Total=N
（N 表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況）。
【輸入樣例】
1 1 0 0 0 0
【輸出樣例】
TOTAL=3
【問題分析】
把問題稍做一個改動，已知 a1+a2+a3+a4+a5+a6 個砝碼的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝碼重量可以相等，求用這些砝碼可稱出的不同重量的個數。
這樣一改就是經典的 0/1 背包問題的簡化版了，求解方法完全和上面說的一樣，這裡就不多說了，只是要注意這個題目不是求最大載重量，是統計所有的可稱出的重量的個數。
【源代碼 1】
program P4;
const
maxn=1010;
w[1..6] of longint=(1,2,3,5,10,20);
var
opt[0..maxn] of boolean;
a[1..6] of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題 7 積木城堡 來源：vijos P1059
【問題描述】
XC 的兒子小 XC 最喜歡玩的遊戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小 XC 是一個比他爸爸 XC 還聰明的孩子，他發現壘城堡的時候，如果下面的積木比上面的積木大，那麼城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規則。
小 XC 想把自己壘的城堡送給幼兒園裡漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起爭執。可是他發現自己在壘城堡的時候並沒有預先考慮到這一點。所以他現在要改造城堡。由於他沒有多餘的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最後的城堡都儘可能的高。
任務：
請你幫助小 XC 編一個程序，根據他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果。
【輸入文件】
第一行是一個整數 N (N0 do
begin
inc(top);
a[top]:=m;
inc(tothig,m);
read(m);
end;
for i:=1 to top do
for j:=tothig downto 1 do
if (j-a[i]>=0) and (opt[ii,j-a[i]]) then
opt[ii,j]:=true;
end;
ans:=maxhig;
while not opt[1,ans] do
dec(ans);
while not can(ans) do
dec(ans);
writeln(ans);
end;
begin
init;
main;
end.
回顧上面的內容充分說明動態規劃的本質就是遞推。其實按照我的理解（動規涉及最優決策，遞推是單純的總結）背包問題的簡化版更準確點算是遞推而非動態規劃，至於動歸和遞推之間的界線本來就很模糊（至少我這麼認為）把它看做什麼都可以，沒必要咬文嚼字。
回到 0/1 背包的原問題上（如果你忘了就去上面看看）。
如果在不知道這個模型的情況下我們怎麼做這個題呢？
這就要用到第一節提到的方法二：三要素法。
題目中明確說明對於一個物品要不就拿走要不就放下，其實題目赤裸裸的告訴我們決策就是不拿（用 0 表示）或拿（用 1 表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應該是很輕鬆的了。
那麼階段是什麼呢？
顯然，給你一堆東西讓你往包裡塞，你當然是一個一個的那來，塞進去。那麼階段很明顯就是物品的個數。
狀態又是什麼呢？
有的人在裝東西是有個習慣（比如說我）就是先把東西分類，然後把同類的東西打個小包，最後在把小包放進去，我們可以按這個思想給物品打一些小包，也就是按照單位為 1 的遞增的順序準備好多小包，比如載重是 6 的包，可以為它準備載重是 1，2，3，4，5 的小包。這樣狀態就可以想出來了：
設計狀態 opt [i，j] 表示裝第 i 個物品時載重為 j 的包可以裝到的最大價值。
opt[i-1,j] (j-w[i]0)
狀態轉移方程：opt [i,j]=
max{opt[i-1,j],opt[i-1,j-w[i]]+v[i]} (j-w[i]>=0,i>0)
(w [i]: 第 i 個物品的重量，v [i] 第 i 個物品的價值)
解釋：要載重為 j 的背包空出 w [i]（j-w [i]）的空間且裝上第 i 個物品，比不裝獲得的價值大就裝上它。
邊界條件：opt [0,i]=0; (i∈{1..S})
註：
這種二維的狀態表示應該在下節講，但是為了方便理解先在這裡說了。
上面的方法動態規劃三要素都很明顯，實現也很簡單。但是在我初學背包時卻用另外一種一維的狀態表示法。
用第一節說的思考方法五（放寬約束和增加約束）在重新思考一下這個問題：
怎麼放寬約束呢？
把題目中的價值去掉，不考慮價值即最優就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？
再一次增加約束：背包只能裝滿。
顯然對於 N 個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那麼裝不滿怎麼辦呢？其實裝不滿背包，它總要達到一定的重量（X）。我們可以把這種情況看作是裝滿一個載重為 X 的小包。
總結一下上面的思維過程：
放寬約束讓我們找到問題的突破口 —— 和背包問題簡化版一樣，我們可以卻定載重為 S 的背包是否可以裝滿。
增加約束讓我們找到問題的求解方法 —— 在裝滿背包的方案中選擇最優的一個方案。
這樣問題就解決了。
設計一個狀態 opt [j] 表示裝滿載重為 j 的背包可獲得的最大價值。對於第 i 個物品，只要 opt [j-w [i]] 可以裝滿且 opt [j-w [i]]+v [i] 比 opt [j] 大就裝上這個物品（更新 opt [j]）。
怎麼使 opt [j] 既有是否構成又有最優的概念呢？
opt [j] 只表示最優，只不過使初始條件 + 1，判斷 opt [j] 是否為 0，如果 opt [j]=0 說明 j 裝不滿。
邊界條件：opt [0]=1;
狀態轉移方程：opt [j]=max {opt [j-w [i]]} (0<i<n,w [i]<=j<=S)
問題解： ans=max {opt [i]}-1 (0<i<=s)
時間複雜度：階段數 O (S)* 狀態數（O (N)）* 轉移代價（O (1)）=O（SN）
下面看幾個例題：
例題 8 採藥 (medic.pas/c/cpp) 來源：NOIP2005（普及組） 第三題
【問題描述】
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裡對他說：「孩子，這個山洞裡有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間裡，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。」
如果你是辰辰，你能完成這個任務嗎？
【輸入文件】
輸入文件 medic.in 的第一行有兩個整數 T（1 <= T <= 1000）和 M（1 <= M <= 100），用一個空格隔開，T 代表總共能夠用來採藥的時間，M 代表山洞裡的草藥的數目。接下來的 M 行每行包括兩個在 1 到 100 之間（包括 1 和 100）的整數，分別表示採摘某株草藥的時間和這株草藥的價值。
【輸出文件】
輸出文件 medic.out 包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值。
【輸入樣例】
70 3
71 100
69 1
1 2
【輸出樣例】
3
【數據規模】
對於 30% 的數據，M <= 10；
對於全部的數據，M y then max:=x
else max:=y;
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
for i:=1 to n do
for j:=1 to t do
if j-w[i]0) and (opt[j-w[i]]+v[i]>opt[j]) then
opt[j]:=opt[j-w[i]]+v[i];
ans:=-maxlongint;
for i:=1 to t do
if opt[i]>ans then ans:=opt[i];
end;
procedure print;
begin
writeln(ans-1);
close(output);
end;
begin
init;
main;
print;
end.
例題 9 開心的金明 來源：NOIP2006（普及組）第二題
【問題描述】
金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過 N 元錢就行」。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的 N 元。於是，他把每件物品規定了一個重要度，分為 5 等：用整數 1~5 表示，第 5 等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過 N 元（可以等於 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第 j 件物品的價格為 v [j]，重要度為 w [j]，共選中了 k 件物品，編號依次為 j1...jk，則所求的總和為：v [j1]*w [j1]+..+v [jk]*w [jk] 請你幫助金明設計一個滿足要求的購物單.
【輸入文件】
輸入的第 1 行，為兩個正整數，用一個空格隔開： N m
（其中 N（<30000）表示總錢數，m (<25) 為希望購買物品的個數。）
從第 2 行到第 m+1 行，第 j 行給出了編號為 j-1 的物品的基本數據，每行有 2 個非負整數 v p
（其中 v 表示該物品的價格（v≦10000），p 表示該物品的重要度（1~5））
【輸出文件】
輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（=0) and (opt [j-v [i]]>0) and (opt [j-v [i]]+v [i]*p [i]>opt [j]) then
opt[j]:=opt[j-v[i]]+v[i]*p[i];
end;
end;
end;
procedure print;
var
i,ans;
begin
ans:=0;
for i:=1 to n do
if opt[i]>ans then
ans:=opt[i];
writeln(ans-1);
end;
begin
init;
main;
print;
end.
例題 10 金明的預算方案 (budget.pas/c/cpp) 來源：NOIP2006 第二題
【問題描述】
金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過 N 元錢就行」。今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬於某個主件的，下表就是一些主件與附件的例子：
主件 附件
電腦 打印機，掃瞄儀
書櫃 圖書
書桌 檯燈，文具
工作椅 無
如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有 0 個、1 個或 2 個附件。附件不再有從屬於自己的附件。金明想買的東西很多，肯定會超過媽媽限定的 N 元。於是，他把每件物品規定了一個重要度，分為 5 等：用整數 1~5 表示，第 5 等最重要。他還從因特網上查到了每件物品的價格（都是 10 元的整數倍）。他希望在不超過 N 元（可以等於 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。
設第 j 件物品的價格為 v [j]，重要度為 w [j]，共選中了 k 件物品，編號依次為 j1，j2，……，jk，則所求的總和為：
v [j1]*w [j1]+v [j2]*w [j2]+ …+v [jk]*w [jk]。（其中 * 為乘號）
請你幫助金明設計一個滿足要求的購物單。
【輸入文件】
輸入文件 budget.in 的第 1 行，為兩個正整數，用一個空格隔開：
N m （其中 N（<32000）表示總錢數，m（<60）為希望購買物品的個數。）
從第 2 行到第 m+1 行，第 j 行給出了編號為 j-1 的物品的基本數據，每行有 3 個非負整數： v p q
（其中 v 表示該物品的價格（v0，表示該物品為附件，q 是所屬主件的編號）
【輸出文件】
輸出文件 budget.out 只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（0 說明花 i 元可以買到物品。這樣就不難設計出這個狀態的轉移方程來：
opt[i]=max{opt[i],opt[i-wj]} ((i-wj>0) and (opt[i-wj]>0)) (0<jy then exit(x);
exit(y);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
opt[0]:=1;
for j:=1 to m do
for i:=n downto v[j] do
if q[j]=0 then
begin
if (i-v[j]>=0) and (opt[i-v[j]]>0) then
opt[i]:=max(opt[i],opt[i-v[j]]+v[j]*p[j]);
if (i-v[j]-v[q1[j]]>=0) and (opt[i-v[j]-v[q1[j]]]>0) then
opt[i]:=max(opt[i],opt[i-v[j]-v[q1[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[j]]);
if (i-v[j]-v[q2[j]]>=0) and (opt[i-v[j]-v[q2[j]]]>0) then
opt[i]:=max(opt[i],opt[i-v[j]-v[q2[j]]]+v[j]*p[j]+v[q2[j]]*p[q2[j]]);
if (i-v[j]-v[q1[j]]-v[q2[j]]>=0) and (opt[i-v[j]-v[q1[j]]-v[q2[j]]]>0) then
opt[i]:=max(opt[i],opt[i-v[j]-v[q1[j]]-v[q2[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[j]]+v[q2[j]]*p[q2[j]]);
ans:=max(ans,opt[i]);
end;
end;
procedure print;
begin
writeln((ans-1)*10);
close(output);
end;
begin
init;
main;
print;
end.
上面提到的幾個例題都是最基礎的題目，而且把問題抽象後就與背包問題的基本模型一樣了，但有些題目用到了基本模型，要求的解卻不一定很模型一樣，下面看個例子：
例題 11 Money Systems (money.pas/c/cpp) 來源：USACO 2.3
【問題描述】
母牛們不但創建了他們自己的政府而且選擇了建立了自己的貨幣系統。[In their own rebellious way],，他們對貨幣的數值感到好奇。
傳統地，一個貨幣系統是由 1,5,10,20 或 25,50, 和 100 的單位面值組成的。
母牛想知道有多少種不同的方法來用貨幣系統中的貨幣來構造一個確定的數值。
舉例來說，使用一個貨幣系統 {1,2,5,10,...} 產生 18 單位面值的一些可能的方法是：18x1, 9x2, 8x2+2x1, 3x5+2+1, 等等其它。寫一個程序來計算有多少種方法用給定的貨幣系統來構造一定數量的面值。保證總數將會適合 long long (C/C++) 和 Int64 (Free Pascal)。
【輸入文件】
貨幣系統中貨幣的種類數目是 V (1<= V<=25)。要構造的數量錢是 N (1<= N<=10,000)。
第 1 行：二整數， V 和 N
第 2 行： 可用的貨幣 V 個整數。
【輸出文件】
單獨的一行包含那個可能的構造的方案數。
【輸入樣例】
3 10
1 2 5
【輸出樣例】
10
【問題分析】
把錢面值，把要構造的前看做載重為 N 的背包，這個問題便是 0/1 背包的簡化版了，但這個問題和傳統模型有所差異，不是判斷 N 是否可構成，而是求構成 N 的方案，而且這裡的面值是可以重複利用的（你可以看做是物品有無限多）。
對與第一個問題，只要把原來 BOOLEAN 型的狀態改為 INT64，在遞推過程中累加方案數即可。
對於第二個問題，基本模型中為了避免重複在內重循環枚舉背包載重時採用倒循環，現在只要正向循環就 OK 了。
複雜度與原模型相同。
【源代碼】
{
ID
PROG
LANG
}
program money;
const
fin='money.in';
fout='money.out';
maxv=100;
maxn=10010;
var
a[0..maxv] of longint;
opt[0..maxn] of int64;
v,n;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(v,n);
for i:= 1 to v do
read(a[i]);
close(input);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
opt[0]:=1;
for i:=1 to v do
for j:=a[i] to n do
inc(opt[j],opt[j-a[i]]);
end;
procedure print;
begin
writeln(opt[n]);
close(output);
end;
begin
init;
main;
print;
end.
背包問題方案的求法：
和大多數 DP 問題的方案的求法一樣，增加一個數組 path 和狀態維數相同用來記錄當前狀態的決策就 OK 了。
輸出方案時候通過當前決策推出上一決策，這一連穿的決策序列就是要求的方案。
下面看這樣一個數據：
載重：6 物品個數：3
重量 價值
物品 1： 3 10
物品 2： 2 2
物品 3： 1 9
一維狀態求解過程：
i=1 : (枚舉物品)
opt[0..6]= 1 0 0 11 0 0 0
path [0..6]=0 0 0 1 0 0 0 {記錄最後裝入包中的物品的編號}
i=2
opt[0..6]=1 0 3 11 0 13 0
path[0..6]=0 0 2 1 0 2 0
i=3
opt[0..6]=1 10 3 12 20 13 22
path[0..6]=0 3 2 3 3 2 3
二維狀態求解過程： （略）
可以看到一維狀態的最優解是正確的，但細心分析發現一個驚人的問題： 方案不對！！
什麼最優解正確而方案不正確呢？
因為在解 i=3 時 opt [6] 用到的方案數應該是 9+2+10=21。顯然這個方案是真確的，所以最優解正確。但是求解完 opt [6] 後，接著求解 opt [3] 卻把原來的 opt [3]=10 改成了 opt [3]=2+9=11 這樣，在整個求解過程結束後最後的方案 opt [6]=9+2+10 就變成了 opt [6]=9+2+2+9 也就是說 1，2 兩個物品裝了兩次。
這也正是我要說的下面的問題；
背包問題一維狀態於二維狀態的優劣：
顯然，一維狀態的維數少空間複雜度低。甚至在一些問題上可以減輕思考負擔。既然這樣是不是我們就應該屏棄二維狀態解法呢？
由於一維狀態在求解方案是存在錯誤，所以二維狀態還是很有用啊。當然有些問題雖然也是在求解方案但要求方案唯一這樣就又可以用一維狀態了。
看到這裡覺得頭暈就上趟廁所，返回來看下面的例題：
例題 12 新年趣事之打牌 來源： vijos P1071
【問題描述】
過年的時候，大人們最喜歡的活動，就是打牌了。xiaomengxian 不會打牌，只好坐在一邊看著。
這天，正當一群人打牌打得起勁的時候，突然有人喊道：「這副牌少了幾張！」眾人一數，果然是少了。於是這副牌的主人得意地說：「這是一幅特製的牌，我知道整副牌每一張的重量。只要我們稱一下剩下的牌的總重量，就能知道少了哪些牌了。」大家都覺得這個辦法不錯，於是稱出剩下的牌的總重量，開始計算少了哪些牌。由於數據量比較大，過了不久，大家都算得頭暈了。
這時，xiaomengxian 大聲說：「你們看我的吧！」於是他拿出筆記本電腦，編出了一個程序，很快就把缺少的牌找了出來。
如果是你遇到了這樣的情況呢？你能辦到同樣的事情嗎？
【輸入文件】
第一行一個整數 TotalW，表示剩下的牌的總重量。
第二行一個整數 N（1<N<=100），表示這副牌有多少張。
接下來 N 行，每行一個整數 Wi（1<=Wi0 then
begin
if opt[j]=0 then
path [j]:=i; {只有當前狀態沒求過才記錄方案}
inc(opt[j],opt[j-w[i]]);
end;
if opt[total]=0 then
begin
writeln('0');
halt;
end;
if opt[total]>1 then
begin
writeln('-1');
halt;
end;
i:=total;
while i>0 do
begin
ans[path[i]]:=false;
i:=i-w[path[i]];
end;
end;
procedure print;
var
i;
begin
for i:=1 to n do
if ans[i] then write(i,' ');
end;
begin
init;
main;
print;
end.
1.3 其它問題
一維動態規劃最常見的就是前面總結的最長下降 / 非降子序列和 0/1 背包問題了，當然還有別的一寫題。由於不是很常見所以沒有固定的解題模式，到時候具體問題具體分析。下面在看一些例子：
例題 13 挖地雷問題 (P3.pas/c/cpp) 來源：NOIP1996（提高組）第三題（有改動）
【問題描述】
在一個地圖上有 N 個地窖（N 3 -> 4 -> 5
max=27
【Hint】
題目中的路徑是有向的且無環路（這是我做的改動原題中沒有要求）。
【問題分析】
看到題目的第一影響是貪心 —— 以一點出發找與他連接的地窖中地雷數最多的一個。
但很容易想到反例：
5
1 2 1 1 100
1 1 0 0
0 1 0
0 1
0
按照貪心答案是 3，但實際上答案是 101。
於是就不得不放棄貪心的想法。
但是貪心給了我們啟示：從一個頂點出發要選擇向一個與他相連且以該點出發可以挖到較多雷的點走。（有點拗口）
另一種解釋：如果一個頂點連同 N 個份量，顯然要則一個較大的就是問題的解答，這個定義是滿足最優化原理的。
那它滿足無後效性麼？
因為圖是有向的，所以以與該頂點相連的點在往下走的路線中不包括該點。也就是說圖是一個 AOV 網（有向無環圖）。
既然滿足最優化原理，且無後效性，我們就可以用動態規劃解了。
這個問題的階段就是拓撲序列，但由於輸入是倒三角形，所以我們沒必要求拓撲序列，只要從 N 到著求解就可以了。
設計狀態 opt [i] 表示以 i 點出發可以挖到最多的雷的個數。
狀態轉移方程：opt [i]=max {opt [j]}+w [i] (g [i,j]=1)
(g 存圖，w [i] 存第 i 個地窖中的雷的個數)。
時間複雜度：
狀態數 O (n)* 轉移代價 O (n)=O (n2)
這個題目還要求出路徑，可以用一個輔助數組 path 來記錄，path [i] 表示從第 i 個出發走到的下一個點的編號。求解完只要按 path 記錄的路徑輸出即可。
【源代碼】
program P3;
const
fin='P3.in';
fout='P3.out';
maxn=200;
var
g[0..maxn,0..maxn] of longint;
n,ans;
w,opt,path[0..maxn] of longint;
procedure init;
var
i,j;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n);
fillchar(g,sizeof(g),0);
for i:=1 to n do
read(w[i]);
for i:=1 to n do
for j:=i+1 to n do
read(g[i,j]);
close(input);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
fillchar(path,sizeof(path),0);
for i:=n downto 1 do
begin
for j:=i+1 to n do
if (g[i,j]=1) and (opt[j]>opt[i]) then
begin
opt[i]:=opt[j];
path[i]:=j;
end;
inc(opt[i],w[i]);
end;
ans:=1;
for i:=2 to n do
if opt[i]>opt[ans] then ans:=i;
end;
procedure print;
var
i;
begin
write(ans);
i:=path[ans];
while i>0 do
begin
write('-->',i);
i:=path[i];
end;
writeln;
writeln('max=',opt[ans]);
close(output);
end;
begin
init;
main;
print;
end.
2. 狀態是二維的
通過前面的學習，我想因該對動態規劃不陌生了，我學習動態規劃是沒這麼系統，二維，一維一起上。二維狀態的動態規劃是重中之重。
所謂二維狀態就是說一般設計的狀態是 opt [i,j] 形式的。那 i,j 可以代表什麼呢？
有很多朋友問過我這個問題，我的回答是：
(1) i,j 組合起來代表一個點的坐標（顯然是平面坐標系）（如：街道問題）。
(2) i,j 組合表示一個矩陣的單元的位置（第 i 行，第 j 列）（如：數塔問題）
(3) 起點為 i 長度為 j 的區間。（如：回文詞）
(4) 起點為 i 終點為 j 的區間。（如：石子合併問題）
(5) 兩個沒關聯的事物，事物 1 的第 i 個位置，對應事物 2 的第 j 個位置（花店櫥窗設計）
(6) 兩個序列，第一個序列的前 i 個位置或第 i 個位置對應第 2 個序列的第 j 個位置或前 j 個位置。（最長公共子序列）。
(7) 其它
下面通過例題和基本模型進一步說明：
2.1 數塔問題
數塔問題來源於一道經典的 IOI 的題目，直接說題通過題目總結公性。以後遇到類似的題目可以參照這個模型。
例題 14 數塔問題 (numtri.pas/c/cpp) 來源：IOI94
【問題描述】
考慮在下面被顯示的數字金字塔。
寫一個程序來計算從最高點開始在底部任意處結束的路徑經過數字的和的最大。每一步可以走到左下方的點也可以到達右下方的點。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的樣例中，從 7 到 3 到 8 到 7 到 5 的路徑產生了最大和：30
【輸入文件】
第一個行包含 R (1<= R<=1000) , 表示行的數目。
後面每行為這個數字金字塔特定行包含的整數。
所有的被供應的整數是非負的且不大於 100。
【輸出文件】
單獨的一行包含那個可能得到的最大的和。
【輸入樣例】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【輸出樣例】
30
【問題分析】
這個問題是學習動態規劃最簡單最經典的問題，說它經典是因為它的階段，狀態決策都十分明顯。
剛看到題目覺得沒有如手點，連怎麼儲存，描述這個金字塔都是問題，看輸入樣例發現：數字金字塔可以變成像輸入樣例那樣的下三角，這樣可以用一個二維數組儲 a 存它，並且可以用（i,j）描述一個數字在金字塔中的位置。
對於中間的一個點來說，想經過它則必須經過它的上方或左上（針對變化後的三角形）。也就是說經過這個點的數字和最大等於經過上方或左上所得的「最大和」中一個更大的加上這個點中的數字。顯然這個定義滿足最優子結構。
這樣階段很明顯就是金字塔的層，設計一個二維狀態 opt [i,j] 表示走到第 i 行第 j 列時經過的數字的最大和。決策就是 opt [i-1,j] 或 opt [i-1,j-1] 中一個更大的加上（i,j）點的數字。
對於一個點只考慮上面或左上即前一階段，滿足無後效性。
狀態轉移方程：
opt[i-1,j]+a[i,j] (j=1)
opt[i,j]= opt[i-1,j-1]+ a[i,j] (j=i)
max {opt [i-1,j],opt [i-1,j-1]}+ a [i,j] (1<j_=0 所以方程也可以這樣寫:
opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j]
同理 j=i 時方程也可以寫成上面那樣，所以方程綜合為：
opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j]（0<j<=i）
顯然答案是走到底後的一個最大值，即：
ans=max{opt[n,i]} (1<=i<=n)
其實從上往下走和從下往上走結果是一樣的，但是如果從下往上走結果就是 opt [1,1] 省下求最大值了，所以方程進一不改動：
opt[i,j]=max{opt[i+1,j],opt[i+1,j+1]}+a[i,j]（0<jopt[i+1,j+1] then
opt[i,j]:=opt[i+1,j]+a[i,j]
else opt[i,j]:=opt[i+1,j+1]+a[i,j];
end;
procedure print;
begin
writeln(opt[1,1]);
close(output);
end;
begin
init;
main;
print;
end._
例題 15 Henry 撿錢 (money.pas/c/cpp) 來源：Dream Team 邀請賽
【問題描述】
最近，Henry 由於失戀 (被某大牛甩掉！) 心情很是鬱悶。所以，他去了大牛家，尋求 Michael 大牛的幫助，讓他盡快從失戀的痛苦中解脫出來.Michael 大牛知道 Henry 是很愛錢的，所以他是費盡腦水，絞盡腦汁想出了一個有趣的遊戲，幫助 Henry.....
Michael 感覺自己簡直是個天才 (我們從不這麼認為), 就把這個遊戲取名為揀錢。為了幫助更多的人採用這種方法早日脫離失戀之苦，Michael 特地選在這次 DT 比賽中把遊戲介紹給大家...(大家鼓掌！！！)
其實，這個遊戲相當垃圾，目的就是為了滿足 Henry 這種具有強烈好錢的心理的人。遊戲是這樣的首先找到了一塊方形的土地，面積為 m*n (米 ^2). 然後他將土地劃分為一平方米大小的方形小格.Michael 在每個格子下都埋有錢 (用非負數 s 表示，表示人民幣的價值為 s) 和炸彈 (用負數 s 表示，表示 Henry 挖出該方格下的東西會花掉 s 的錢去看病，醫炸彈炸傷的傷口)... 遊戲的要求就是讓 Henry 從一側的中間列出發，按照下圖的 5 種方式前進（前進最大寬度為 5）, 不能越出方格。他每到一個格子，必定要取走其下相應的東西。直到到達土地的另一側，遊戲結束。不用說也知道，Henry 肯定想得到最多的人民幣。所以他偷窺了，Michael 埋錢的全過程，繪成了一張距陣圖。由於他自己手動找會很麻煩，於是他就找到了學習編程的你。請給幫他找出，最大人民幣價值.
揀錢路線規則 (只有 5 個方向，如下圖)：
H 為 Henry 的出發點，每組數據的出發點都是最後一行的中間位置！
(前方 5 個格子為當前可以到達的)
【輸入文件】
第一行為 m n.(n 為奇數)，入口點在最後一行的中間
接下來為 m*n 的數字距陣.
共有 m 行，每行 n 個數字。數字間用空格隔開。代表該格子下是錢或炸彈.
為了方便 Henry 清算，數字全是整數.
【輸出文件】
一個數，為你所找出的最大人民幣價值.
【輸入樣例】
6 7
16 4 3 12 6 0 3
4 -5 6 7 0 0 2
6 0 -1 -2 3 6 8
5 3 4 0 0 -2 7
-1 7 4 0 7 -5 6
0 -1 3 4 12 4 2
【輸出樣例】
51
【數據範圍】
N and M<=200.
結果都在 longint 範圍內
【問題分析】
去掉題目華麗的偽裝，我們可以這樣描述這個題目：
給定一個數字矩陣，從最後一層的中間出發可以向圖上所示的 5 個方向走，直到走到第一層，使經過的數字和最大。
如果我們不考慮負數對問題的影響，這個問題的描述就是經典的數塔問題了，只不過將塔變成了矩陣。
這樣就可以用剛剛講過的數塔問題的模型解這個題目了，我就不多說了。
狀態轉移方程：
opt[i,j]=max(opt[i-1,k])+a[i,j] (j-2<=k0) and (kmax) then
max:=opt[i-1,k];
opt[i,j]:=max+a[i,j];
end;
ans:=-maxlongint;
i:=(1+m) div 2;
for j:=i-2 to i+2 do
if (j>0) and (jans) then
ans:=opt[n,j];
end;
procedure print;
begin
writeln(ans);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
2.2 街道問題
和數塔問題一樣街道問題也來源於一道典型的例題，下面我們看一下這道題。
例題 16 街道問題 (way.pas/c/cpp) 來源：《奧賽經典》（提高篇）
【問題描述】
如圖所示的矩形圖中找到一條從左下角到右上角的最短路徑，圖中數字表示邊的長度。只能向右或向上走。
【輸入文件】第一行兩個數，N，M 矩形的點有 N 行 M 列。（0<N，M<1000）接下來 N 行每行 M-1 個數描述橫向邊的長度。接下來 N-1 行每行 M 個數描述縱向邊的長度。邊的長度小於 10。
【輸出文件】一個數 —— 最短路徑長度。
【輸入樣例】
4 5
3 7 4 8
4 6 3 5
3 6 3 5
5 4 6 2
7 6 3 5 3
2 8 5 9 4
8 7 4 3 7
【輸出樣例】
28
【問題分析】
因為只能向右或向上走，所以階段應該是這樣的：
如果把圖再做個改動看看：
這樣就想是上面說的數塔問題了，只不過數塔問題的數在點上而街道問題的數在邊上。但是並不影響問題的求解我們可以用數塔問題的思路來解這個問題。
設計一個二維狀態 opt [i,j] 表示走到（i,j）的最短路徑，顯然這個路徑只可能是左邊或上邊走來的，所以決策就是這兩個方向上加上經過的邊的和中一個較短的路。於是有下面的狀態轉移方程：
opt[i+1,j]+z[i,j] (j=1)
opt[i,j]＝ opt[i,j-1]+h[i,j] (i=n)
min{opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]} (0<i<=n,0<j<=m)
和數塔問題一樣，這個問題也可以做類似的預處理：初始化 opt 的值是一個很大的數，保證解不會超過他，但要注意不要太的了，太大了可能有２２５問題。opt [0,0]=0。這樣就可以把方程整理為：
opt[i,j]= min{opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]}
複雜度：狀態數 O（N2）* 轉移代價 O（1）=O（N2）
這一類問題是很經典的問題。
思考這樣一個問題：如果讓找出一條最短路徑，一條較短路徑，且兩條路徑不重合該怎麼辦呢？
這個問題先留給大家思考，在後面的多維狀態中會詳細的講。
【源代碼】
program way;
const
fin='way.in';
fout='way.out';
maxn=1010;
var
h,z,opt[0..maxn,0..maxn] of longint;
n,m;
procedure init;
var
i,j;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n,m);
for i:=1 to n do
for j:=2 to m do
read(h[i,j]);
for i:=1 to n-1 do
for j:=1 to m do
read(z[i,j]);
close(input);
end;
function min(x,y);
begin
min:=y;
if x<y then min:=x;
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),$7F);
opt[n,0]:=0;
for i:=n downto 1 do
for j:=1 to m do
opt[i,j]:=min(opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]);
end;
procedure print;
begin
writeln(opt[1,m]);
close(output);
end;
begin
init;
main;
print;
end.
還有一道例題是街道問題的變形在記憶化搜索處會說。
2.3 最長公共子序列問題
和前面講的有所區別，這個問題的不涉及走向。很經典的動態規劃問題。
例題 17 最長公共子序列 (lcs.pas/c/cpp) 來源：《全國青少年信息學奧林匹克聯賽培訓教材》
【問題描述】
一個給定序列的子序列是在該序列中刪去若干元素後得到的序列。確切地說，若給定序列 X= ，則另一序列 Z= 是 X 的子序列是指存在一個嚴格遞增的下標序列 ，使得對於所有 j=1,2,…,k 有 Xij=Zj
例如，序列 Z = 是序列 X = 的子序列，相應的遞增下標序列為。給定兩個序列 X 和 Y，當另一序列 Z 既是 X 的子序列又是 Y 的子序列時，稱 Z 是序列 X 和 Y 的公共子序列。例如，若 X= 和 Y= ，則序列是 X 和 Y 的一個公共子序列，序列也是 X 和 Y 的一個公共子序列。而且，後者是 X 和 Y 的一個最長公共子序列，因為 X 和 Y 沒有長度大於 4 的公共子序列。
給定兩個序列 X= 和 Y= ，要求找出 X 和 Y 的一個最長公共子序列。
【輸入文件】
輸入文件共有兩行，每行為一個由大寫字母構成的長度不超過 200 的字符串，表示序列 X 和 Y。
【輸出文件】
輸出文件第一行為一個非負整數，表示所求得的最長公共子序列的長度，若不存在公共子序列，則輸出文件僅有一行輸出一個整數 0，否則在輸出文件的第二行輸出所求得的最長公共子序列 (也用一個 大寫字母組成的字符串表示。
【輸入樣例】
ABCBDAB
BDCBA
【輸出樣例】
4
BCBA
【問題分析】
這個問題也是相當經典的。。
這個題目的階段很不明顯，所以初看這個題目沒什麼頭緒，不像前面講的有很明顯的上一步，上一層之類的東西，只是兩個字符串而且互相沒什麼關聯。
但仔細分析發現還是有入手點的：
既然說是動態規劃，那我們首先要考慮的就是怎麼劃分子問題，一般對於前面講到的街道問題和數塔問題涉及走向的，考慮子問題時當然是想上一步是什麼？但這個問題沒有涉及走向，也沒有所謂的上一步，該怎麼辦呢？
既然是求公共子序列，也就有第一個序列的第 i 個字符和第二個序列的第 j 個字符相等的情況。
那麼我們枚第一個序列（X）的字符，和第二個序列（Y）的字符。
顯然如果 X [i]=Y [j] 那麼起點是 1（下面說的子序列都是起點為 1 的），長度為 i 的子序列和長度為 j 的子序列的最長公共子序列就是長度為 i-1 和長度為 j-1 的子序列中最長的公共子序列加上 X [i] 或 Y [j]。
那要是不相等呢？
如果不相等，也就是說第一個序列長度為 I 的子序列和第二個序列中長度為 j 的子序列的公共子序列中 X [i] 和 Y [j] 不同時出現。也就是說第一個序列長度為 i 的子序列和第二個序列中長度為 j 的子序列的公共子序列是第一個序列長度為 i 的子序列和第二個序列中長度為 j-1 的子序列或第一個序列長度為 i-1 的子序列和第二個序列中長度為 j 的子序列的公共子序列中一個更長的。
設計一個狀態 opt [i,j] 表示起點為 1，第一序列長度為 i，第二序列長度為 j 的子序列的最長公共子序列。按照上面的分類就可以得到狀態轉移方程：
opt[i-1,j-1]+x[i] (x[i]=y[j])
opt[i,j]= opt[i-1,j]+x[i] (length(opt[i-1,j])>=length(opt[i,j-1]))
opt[i,j-1]+y[j] (length(opt[i-1,j])<length(opt[i,j-1]))
(0<i<=length(X),0<j=length(opt[i,j-1]) then
opt[i,j]:=opt[i-1,j]
else opt[i,j]:=opt[i,j-1];
end;
procedure print;
begin
writeln(length(opt[L1,L2]));
write(opt[L1,L2]);
close(output);
end;
begin
init;
main;
print;
end.
例題 18 回文詞 (palin.pas/c/cpp) 來源：IOI 2000
【問題描述】
回文詞是一種對稱的字符串 —— 也就是說，一個回文詞，從左到右讀和從右到左讀得到的結果是一樣的。任意給定一個字符串，通過插入若干字符，都可以變成一個回文詞。你的任務是寫一個程序，求出將給定字符串變成回文詞所需插入的最少字符數。
比如字符串「Ab3bd」，在插入兩個字符後可以變成一個回文詞（「dAb3bAd」或「Adb3bdA」）。然而，插入兩個以下的字符無法使它變成一個回文詞。
【輸入文件】
第一行包含一個整數 N，表示給定字符串的長度，3<=Ny then exit (x);
max:=y;
end;
procedure main;
var
i,x,j,k0,k1;
begin
fillchar(opt,sizeof(opt),0);
readln(n);
readln(a);
b:='';
for i:=n downto 1 do
b:=b+a[i];
k0:=0;
k1:=1;
for i:=1 to n do
begin
fillchar(opt[k1],sizeof(opt[k1]),0);
for j:=1 to n do
begin
opt[k1,j]:=max(opt[k0,j],opt[k1,j-1]);
if a[i]=b[j] then
opt[k1,j]:=max(opt[k1,j],opt[k0,j-1]+1);
end;
x:=k0;
k0:=k1;
k1:=x;
end;
writeln(n-opt[k0,n]);
end;
begin
main;
end.
用這個方法 AC 了就該很高興了，但不要停止思考的步伐，還有別的方法麼？
從原問題出發，找這個問題的子問題。和上面說的最長公共子序列問題一樣，設計序列的問題我們一般要考慮它的子序列，也就是更短的序列。
這樣就回到了我第一節說的邊界條件法了。
顯然單獨的字符就是邊界了，而且單獨的字符就是回文詞，添加 0 個字符就可以了。
如果是兩個字符組成的序列怎麼辦呢？
只要看他們是否相同就可以了，如果相同那就是回文詞了，添加 0 個字符，如果不相同就在它的左邊或右邊添一個字符，讓另外一個當對稱軸。
如果是 3 個字符呢？
我們用 S 存這個序列，如果 S [1]=S [3] 那麼它就是回文詞了，
如果 S [1] S [3] 那麼就在前面添 S [3] 或後面添 S [1]
剩下的就要考慮 S [1] S [2] 和 S [2] S [3] 這兩個序列了。
通過前面的分析我們很容易想到這樣的算法：
對於一個序列 S 只要看它的左右端的字符是否相同，如果相同那麼就看除掉兩端字符的新串要添的字符個數了；如果不同，就在它左面添上右斷的字符然後考慮去掉新序列兩端的字符後的串要添的字符。或者在右面添上左端的字符，在考慮去掉添了字符後新串左右兩端字符得到的新串要添的字符。
設計一個二維狀態 opt [L,i] 表示長度是 L+1，起點是 i 的序列變成回文詞要添的字符的個數。階段就是字符的長度，決策要分類，即 S [i] 和 S [i+L] 是否相等。
狀態轉移方程:
min(opt[L-1,i]+1, opt[L-1,i+1]+1) (s[i]s[i+L])
opt[L,i]=
min(opt[L-1,i]+1, opt[L-1,i+1]+1,opt[L-2,i+1]) (s[i]=s[i+L])
複雜度：
空間複雜度 = 狀態數 O（N2）
時間複雜度 = 狀態數 O（N2）* 轉移代價 O（1）=O（N2）
由於空間複雜度較高，仍然要用滾動數組。
【源代碼 2】
program P1327;
const
maxn=5002;
var
a[0..maxn] of char;
opt[0..2,0..maxn] of longint;
n,ans;
function min(x,y);
begin
min:=y;
if x<y then min:=x;
end;
procedure main;
var
i,L,j,k0,k1,k2;
begin
fillchar(opt,sizeof(opt),0);
readln(n);
for i:=1 to n do
read(a[i]);
k0:=0;
k1:=1;
k2:=2;
for L:=1 to n-1 do
begin
for i:=1 to n-L do
begin
opt[k2,i]:=min(opt[k1,i],opt[k1,i+1])+1;
if a[i]=a[i+L] then
opt[k2,i]:=min(opt[k2,i],opt[k0,i+1]);
end;
j:=k0;
k0:=k1;
k1:=k2;
k2:=j;
end;
writeln(opt[k1,1]);
end;
begin
main;
end.
例題 19 調整隊形 (queue.pas/c/cpp) 來源：TJU P1006
【問題描述】
學校藝術節上，規定合唱隊要參加比賽，各個隊員的衣服顏色不能很混亂：合唱隊員應排成一橫排，且衣服顏色必須是左右對稱的。
例如：「紅藍綠藍紅」或「紅藍綠綠藍紅」都是符合的，而「紅藍綠紅」或「藍綠藍紅」就不符合要求。
合唱隊人數自然很多，僅現有的同學就可能會有 3000 個。老師希望將合唱隊調整得符合要求，但想要調整儘量少，減少麻煩。以下任一動作認為是一次調整：
1、在隊伍左或右邊加一個人（衣服顏色依要求而定）；
2、在隊伍中任兩個人中間插入一個人（衣服顏色依要求而定）；
3、剔掉一個人；
4、讓一個人換衣服顏色；
老師想知道就目前的隊形最少的調整次數是多少，請你編一個程序來回答他。
因為加入合唱隊很熱門，你可以認為人數是無限的，即隨時想加一個人都能找到人。同時衣服顏色也是任意的。
【輸入文件】
第一行是一個整數 n (1≦n≦3000)。
第二行是 n 個整數，從左到右分別表示現有的每個隊員衣服的顏色號，都是 1 到 3000 的整數。
【輸出文件】
一個數，即對於輸入隊列，要調整得符合要求，最少的調整次數。
【輸入樣例】
5
1 2 2 4 3
【輸出樣例】
2
【問題分析】
讀完題目發現很熟悉，仔細想想這個題就是回文詞的加強版。不同與回文詞的是這個問題的決策多了，不僅可以插入一個人（詞），還可以剔人，還可以換服裝，其實剔人和插入是等價的。也就是說比原問題只多了一個條件就是可以換服裝。
這樣就不能用回文詞的第一個方法解了。（因為序列中的元素不固定，可以換）。只能用第二個方法解。
和回文詞一樣，階段是序列的長度，狀態是 opt [i,j] 表示 [i,j] 這段區間內要變成回文所需要的最少的調整次數。
決策比回文詞多了一個，即：如果左右兩端不一樣還可以通過換服裝這種方式只花費一次的代價調整好。
狀態轉移方程：
min{opt[i,j-1]+1,opt[i+1,j]+1,opt[i+1,j-1]+1}
opt[i,j]= (a[i]a[j],1<=i<j<=n)
min{opt[i,j-1]+1,opt[i+1,j]+1,opt[i+1,j-1]}
(a[i]=a[j],1<=i<j<=n)
邊界條件[i,i]=0 (1<=i<=n)
時間複雜度：
狀態數 O（N2）* 轉移代價 O（1）= 總複雜度 O（N2）
【源代碼】
program queue;
const
fin='queue.in';
fout='queue.out';
maxn=3000;
var
a[0..maxn] of longint;
opt[0..maxn,0..maxn] of longint;
n;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j,L;
begin
fillchar(opt,sizeof(opt),0);
for L:=1 to n-1 do
for i:=1 to n-L do
begin
j:=i+L;
if opt[i+1,j]+1<opt[i,j-1]+1 then
opt[i,j]:=opt[i+1,j]+1
else opt[i,j]:=opt[i,j-1]+1;
if a[i]=a[j] then
begin
if opt[i+1,j-1]<opt[i,j] then
opt[i,j]:=opt[i+1,j-1]
end
else begin
if opt[i+1,j-1]+1<opt[i,j] then
opt[i,j]:=opt[i+1,j-1]+1;
end;
end;
end;
procedure print;
begin
writeln(opt[1,n]);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
2.4 背包問題的拓展
前面說的背包問題還有個有趣的變形，可以說是背包問題的拓展吧，下面看一下這個例題：
例題 20 找啊找啊找 GF (gf.pas/c/cpp) 來源：MM 群 2007 七夕模擬賽（RQNOJ 57）
【問題描述】
"找啊找啊找 GF, 找到一個好 GF, 吃頓飯啊拉拉手，你是我的好 GF. 再見."
"誒，別再見啊..."
七夕... 七夕... 七夕這個日子，對於 sqybi 這種單身的菜鳥來說是多麼的痛苦... 雖然他聽著這首叫做 "找啊找啊找 GF" 的歌，他還是很痛苦。為了避免這種痛苦，sqybi 決定要給自己找點事情幹。他去找到了七夕模擬賽的負責人 zmc MM, 讓她給自己一個出題的任務。經過幾天的死纏爛打，zmc MM 終於同意了.
但是，拿到這個任務的 sqybi 發現，原來出題比單身更讓人感到無聊 -_-.... 所以，他決定了，要在出題的同時去辦另一件能夠使自己不無聊的事情 -- 給自己找 GF.
sqybi 現在看中了 n 個 MM, 我們不妨把她們編號 1 到 n. 請 MM 吃飯是要花錢的，我們假設請 i 號 MM 吃飯要花 rmb [i] 塊大洋。而希望騙 MM 當自己 GF 是要費人品的，我們假設請第 i 號 MM 吃飯試圖讓她當自己 GF 的行為 (不妨稱作泡該 MM) 要耗費 rp [i] 的人品。而對於每一個 MM 來說，sqybi 都有一個對應的搞定她的時間，對於第 i 個 MM 來說叫做 time [i]. sqybi 保證自己有足夠的魅力用 time [i] 的時間搞定第 i 個 MM^_^.
sqybi 希望搞到儘量多的 MM 當自己的 GF, 這點是毋庸置疑的。但他不希望為此花費太多的時間 (畢竟七夕賽的題目還沒出), 所以他希望在保證搞到 MM 數量最多的情況下花費的總時間最少.
sqybi 現在有 m 塊大洋，他也通過一段時間的努力攢到了 r 的人品 (這次為模擬賽出題也攢 rp 哦～～). 他憑藉這些大洋和人品可以泡到一些 MM. 他想知道，自己泡到最多的 MM 花費的最少時間是多少.
注意 sqybi 在一個時刻只能去泡一個 MM-- 如果同時泡兩個或以上的 MM 的話，她們會打起來的...
【輸入文件】
輸入的第一行是 n, 表示 sqybi 看中的 MM 數量.
接下來有 n 行，依次表示編號為 1, 2, 3, ..., n 的一個 MM 的信息。每行表示一個 MM 的信息，有三個整數, rp 和 time.
最後一行有兩個整數，分別為 m 和 r.
【輸出文件】
你只需要輸出一行，其中有一個整數，表示 sqybi 在保證 MM 數量的情況下花費的最少總時間是多少.
【輸入樣例】
4
1 2 5
2 1 6
2 2 2
2 2 3
5 5
【輸出樣例】
13
【數據規模】
對於 20% 數據，1<=n<=10;
對於 100% 數據，1<=rmb<=100,1<=rp<=100,1<=time<=1000;
對於 100% 數據，1<=m<=100,1<=r<=100,1<=n0 說明花費正好)
狀態轉移方程：
opt[j,k]=max{opt[j-rmb[i],k-rp[i]]+1}
(rmb[i]<=j<=m,rp[i]<=k<=r,0<i0)
ct[j,k]:=min{ct[j-rmb[i],k-rp[i]]}+time[i] (opt[j,k]=opt[j-rmb[i],k-rp[i]]+1)
時間複雜度：
階段數 O（N）* 狀態數 O（MR）* 轉移代價 O（1）= O（NMR）
註：數據挺小的。
問題拓展：
如果要加入別的條件，比如泡 MM 還要一定的 SP，等也就是說一個價值要不同的條件確定，那麼這個問題的狀態就需要在加一維，多一個條件就多一維。
【源代碼】
program gf;
const
fin='gf.in';
fout='gf.out';
maxn=110;
var
rmb,rp,time[0..maxn] of longint;
opt,ct[0..maxn,0..maxn] of longint;
n,m,r,ans,max;
procedure init;
var
i;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n);
for i:=1 to n do
read(rmb[i],rp[i],time[i]);
read(m,r);
close(input);
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),0);
fillchar(ct,sizeof(ct),0);
opt[0,0]:=1;
for i:=1 to n do
for j:=m downto rmb[i] do
for k:=r downto rp[i] do
if opt[j-rmb[i],k-rp[i]]>0 then
begin
if opt[j-rmb[i],k-rp[i]]+1>opt[j,k] then
begin
opt[j,k]:=opt[j-rmb[i],k-rp[i]]+1;
ct[j,k]:=ct[j-rmb[i],k-rp[i]]+time[i];
end
else if (opt[j-rmb[i],k-rp[i]]+1=opt[j,k])
and (ct[j-rmb[i],k-rp[i]]+time[i]max then
begin
max:=opt[j,k];
ans:=ct[j,k];
end
else if (opt [j,k]=max) and (ct [j,k] 0），打分越高的碟說明多多越愛看。每張碟有播放的時間 Ti。多多想在今晚爺爺規定的時間裡看的碟總分最高。（必須把要看的碟看完，也就是說一張碟不能只看一半）。顯然叔叔在買碟是沒必要把 N 張全買了，只要買要看的就 OK 了，這樣節省資金啊。而且多多讓叔叔慣的特別任性只要他看到有幾張就一定會看完。
可是出現了一個奇怪的問題，買碟的地方只買給顧客 M（M<N）張碟，不會多也不會少。這可讓多多叔叔為難了。怎麼可以在 N 張碟中只買 M 張而且在規定時間看完，而且使總價值最高呢？
聰明的你幫幫多多的叔叔吧。
【輸入說明】(watchdvd.in)
輸入文件有三行
第一行：兩個數空格隔開的正整數，N，M，L（分別表示叔叔給多多買的碟的數量，商店要買給叔叔的碟的數量，爺爺規定的看碟的時間段）。
第二行到第 N 行，每行兩個數：T，M，給出多多列表中 DVD 碟的信息。
【輸出說明】(watchdvd.out)
單獨輸出一行
表示多多今晚看的碟的總分。
如果商店賣給叔叔的 M 張碟無法在爺爺規定的時間看完輸出 0；
【輸入樣例】
3 2 10
11 100
1 2
9 1
【輸出樣例】
3
【數據範圍】
20% 的數據 N <=20; L<=2000;
100% 的數據 N<=100 L<=2000; M y then max:=x;
end;
procedure main;
var
i,j,k;
begin
fillchar(opt,sizeof(opt),0);
for i:=1 to n do
for j:=m downto 1 do
if j0) or ((j=1) and (k=w[i])) then
opt[j,k]:=max(opt[j-1,k-w[i]]+val[i],opt[j,k]);
ans:=-maxlongint;
for i:=0 to v do
if opt[m,i]>ans then ans:=opt[m,i];
end;
procedure print;
begin
write(ans);
close(output);
end;
begin
init;
main;
print;
end.
2.5 石子合併問題
也有人把這類問題叫做是區間上的動態規劃。
例題 22 石子合併 (stone.pas/c/cpp) 來源：某年 NOI（去巴蜀交）
【問題描述】
在一個操場上擺放著一行共 n 堆的石子。現要將石子有序地合併成一堆。規定每次只能選相鄰的兩堆合併成新的一堆，並將新的一堆石子數記為該次合併的得分。請編輯計算出將 n 堆石子合併成一堆的最小得分和將 n 堆石子合併成一堆的最大得分。
【輸入文件】
輸入第一行為 n (n<1000)，表示有 n 堆石子，第二行為 n 個用空格隔開的整數，依次表示這 n 堆石子的石子數量（y then max:=x;
end;
function min(x,y);
begin
min:=y;
if (x0) then min:=x;
end;
procedure main;
var
i,j,L,k;
begin
fillchar(minopt,sizeof(minopt),200);
fillchar(maxopt,sizeof(maxopt),0);
for i:=1 to 2*n do
minopt[i,i]:=0;
for L:=1 to n-1 do
for i:=1 to 2*n-L do
begin
j:=i+L;
for k:=i to j-1 do
begin
maxopt[i,j]:=max(maxopt[i,j],maxopt[i,k]+maxopt[k+1,j]);
minopt[i,j]:=min(minopt[i,j],minopt[i,k]+minopt[k+1,j]);
end;
inc(maxopt[i,j],sum[j]-sum[i-1]);
inc(minopt[i,j],sum[j]-sum[i-1]);
end;
maxans:=-maxlongint;
minans:=maxlongint;
for i:=1 to n do
maxans:=max(maxans,maxopt[i,i+n-1]);
for i:=1 to n do
minans:=min(minans,minopt[i,i+n-1]);
{for i:=1 to n*2 do
begin
for j:=1 to n*2 do
write(maxopt[i,j],' ');
writeln;
end;}
end;
begin
init;
main;
writeln(minans,' ',maxans);
end.
例題 23 能量項鏈 (energy.pas/c/cpp) 來源 NOIP2006（提高組）
【問題描述】
在 Mars 星球上，每個 Mars 人都隨身佩帶著一串能量項鏈。在項鏈上有 N 顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數。並且，對於相鄰的兩顆珠子，前一顆珠子的尾標記一定等於後一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是 Mars 人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標記為 m，尾標記為 r，後一顆能量珠的頭標記為 r，尾標記為 n，則聚合後釋放的能量為（Mars 單位），新產生的珠子的頭標記為 m，尾標記為 n。
需要時，Mars 人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鏈釋放出的總能量最大。
例如：設 N=4，4 顆珠子的頭標記與尾標記依次為 (2，3) (3，5) (5，10) (10，2)。我們用記號⊕表示兩顆珠子的聚合操作，(j⊕k) 表示第 j，k 兩顆珠子聚合後所釋放的能量。則第 4、1 兩顆珠子聚合後釋放的能量為：
(4⊕1)=10*2*3=60。
這一串項鏈可以得到最優值的一個聚合順序所釋放的總能量為
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【輸入文件】
輸入文件 energy.in 的第一行是一個正整數 N（4≦N≦100），表示項鏈上珠子的個數。第二行是 N 個用空格隔開的正整數，所有的數均不超過 1000。第 i 個數為第 i 顆珠子的頭標記（1≦i≦N），當 i2 3 5 10 2 3 5 10
這樣處理後其中任意長度為 N+1 的鏈就可代表一個環，那麼問題就轉化成合併任意長度為 N+1 的鏈所能釋放的總能量最大。
也就是說從任意一點 (i<k<j) 把鏈拆成兩段問題的解就是合併這兩段釋放出最大能量在加上合併後這兩顆珠子再一次合併釋放的能量。將這個子問題進一步分解就是分解到鏈長度為 1 也就是就有兩課珠子時，生成這兩顆柱子沒有釋放能量，而合併他們釋放的能量是 m*r*n。（這就是邊界條件）。
我們設計一個狀態 opt [i,j] 表示合併頭為 i，尾為 j 的鏈狀項鏈所能釋放的最多的能量值。邊界條件是 opt [i,i]=0 (1<=i<=n*2).
根據定義不難得到動規的狀態轉移方程:
opt[i,j]=max{opt[i,j],opt[i,k]+opt[k,j]+a[i]*a[k]*a[j]}(i<ky then exit(x);
exit(y);
end;
procedure main;
var
i,j,k,L;
begin
fillchar(opt,sizeof(opt),0);
for L:=2 to n do
for i:=1 to n*2-L+1 do
begin
j:=i+L;
for k:=i+1 to j-1 do
opt[i,j]:=max(opt[i,j],opt[i,k]+opt[k,j]+a[i]*a[j]*a[k]);
end;
for i:=1 to n do
ans:=max(ans,opt[i,i+n]);
end;
procedure print;
begin
writeln(ans);
close(output);
end;
begin
init;
main;
print;
end.
例題 24 統計單詞個數 (.pas/c/cpp) 來源：NOIP2001（提高組）
【問題描述】
給出一個長度不超過 200 的由小寫英文字母組成的字母串 (約定；該字串以每行 20 個字母的方式輸入，且保證每行一定為 20 個)。要求將此字母串分成 k 份 (1<k<=40)，且每份中包含的單詞個數加起來總數最大 (每份中包含的單詞可以部分重疊。當選用一個單詞之後，其第一個字母不能再用。例如字符串 this 中可包含 this 和 is，選用 this 之後就不能包含 th)。
單詞在給出的一個不超過 6 個單詞的字典中。
要求輸出最大的個數。
【輸入文件】
去部輸入數據放在文本文件 input3.dat 中，其格式如下：
每組的第一行有二個正整數 (p，k)
p 表示字串的行數；
k 表示分為 k 個部分。
接下來的 p 行，每行均有 20 個字符。
再接下來有一個正整數 s，表示字典中單詞個數。(1<=s<=6)
接下來的 s 行，每行均有一個單詞。
【輸出文件】
結果輸出至屏幕，每行一個整數，分別對應每組測試數據的相應結果。
【輸入樣例】
1 3
thisisabookyouareaoh
4
is
a
ok
sab
【輸出樣例】
7
【問題分析】
剛看到這個題目覺得很迷茫，沒入手點但是突然看到了閃亮的突破口：題目中說 this 包含 this 和 is 但不包含 th 這也就是說在一個串內對於一個固定了起點的單詞只能用一次，即使他還可以構成別的單詞但他還是用一次。比如：串：thisa
字典：this is th
串中有 this is th 這三個單詞，但是對於 this 和 th 只用一次，也就是說枚舉一下構成單詞的起點，只要以該起點的串中包含可以構成一個以該起點開頭的單詞，那麼就說明這個串中多包含一個單詞。
這樣可一得出下面的結果：
每舉的起點 結論：
t 至少包含 1 個
h 至少包含 1 個
i 至少包含 2 個
s 至少包含 2 個
a 至少包含 2 個
考慮到這裡，就有點眉目了。
題目中要將串分 K 個部分也就是說從一個點截斷後一個單詞就未必可以構成了。比如上例要分 3 個部分合理的其中的一個部分至多有 3 個字母，這樣 this 這個單詞就構不成了。
要是分 5 個部分，那就連一個單詞都夠不成了。
這樣就需要對上面做個改動，上面的只控制了起點，而在題目中還需要限制終點，分完幾個部分後，每部分終點不同可以構成的單詞就不同了。
這樣就需要再枚舉終點了。
設計一個二維數組 sum [i,j] 統計從 i 到 j 的串中包含的單詞的個數
狀態轉移方程:
sum [i+1,j]+1 (s [i,j] 中包含以 S [i] 開頭的單詞)
sum[i,j]=
sum [i+1,j] (與上面相反)
註：(1) 這裡枚舉字符的起點的順序是從尾到頭的。
(2) 有人把上面這次也看做是一次動態規劃，但我覺得更準確的說是遞推。
求出所有的 SUM 還差一步，就是不同的劃分方法顯然結果是不一樣的，但是對於求解的問題我們可以這樣把原問題分解成子問題：求把一個串分成 K 部分的最多單詞個數可以看做是先把串的最後一部分分出來，在把前面一部分分解成 K-1 個部分，顯然決策就是找到一種劃分的方法是前面的 K-1 部分的單詞 + 最後一部分的單詞最多。
顯然這個問題滿足最優化原理，那滿足不滿足無後效性呢？
對於一個串分解出最後一部分在分解前面的那部分是更本就不會涉及分好的這部分，換句話說沒次分解都回把串分解的更小，對於分解這個更小的傳不會用到不屬於這個小串的元素。這就滿足無後效性。
具體求解過程：
設計一個狀態 opt [i,j] 表示把從１到 j 的串分成 i 份可以得到最多的單詞的個數。決策就是枚舉分割點使當前這種分割方法可以獲得最多的單詞。
狀態轉移方程：opt [I,j]=max (opt [i-1,t]+sum [t+1,j]) (i<t<j)
邊界條件：opt [1,i]=sum [1,i] (0<iy then max:=x;
end;
procedure main;
var
i,j,t;
begin
L:=length(s);
for i:=L downto 1 do
for j:=i to L do
if find(i,j) then sum[i,j]:=sum[i+1,j]+1
else sum[i,j]:=sum[i+1,j];
fillchar(opt,sizeof(opt),0);
opt[1]:=sum[1];
for i:=2 to k do
for j:=i+1 to L do
for t:=i+1 to j-1 do
opt[i,j]:=max(opt[i,j],opt[i-1,t]+sum[t+1,j]);
writeln(opt[k,L]);
end;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
init;
main;
close(input);
close(output);
end.
2.6 其他問題
還有一些題目雖和一寫基本模型相似但又有區別，我也就不總結共性了，列出它們，看看他們的狀態又是怎麼設計的：
例題 25 花店櫥窗設計 (flower.pas/c/cpp) 來源：IOI 或巴蜀評測系統
【問題描述】假設以最美觀的方式佈置花店的櫥窗，有 F 束花，每束花的品種都不一樣，同時，至少有同樣數量的花瓶，被按順序擺成一行，花瓶的位置是固定的，並從左到右，從 1 到 V 順序編號，V 是花瓶的數目，編號為 1 的花瓶在最左邊，編號為 V 的花瓶在最右邊，花束可以移動，並且每束花用 1 到 F 的整數惟一標識，標識花束的整數決定了花束在花瓶中列的順序即如果 I < J，則花束 I 必須放在花束 J 左邊的花瓶中。
例如，假設杜鵑花的標識數為 1，秋海棠的標識數為 2，康乃馨的標識數為 3，所有的花束在放人花瓶時必須保持其標識數的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數目大於花束的數目，則多餘的花瓶必須空，即每個花瓶中只能放一束花。
每一個花瓶的形狀和顏色也不相同，因此，當各個花瓶中放人不同的花束時會產生不同的美學效果，並以美學值 (一個整數) 來表示，空置花瓶的美學值為 0。在上述例子中，花瓶與花束的不同搭配所具有的美學值，可以用如下表格表示。
根據表格，杜鵑花放在花瓶 2 中，會顯得非常好看，但若放在花瓶 4 中則顯得很難看。
為取得最佳美學效果，必須在保持花束順序的前提下，使花的擺放取得最大的美學值，如果具有最大美學值的擺放方式不止一種，則輸出任何一種方案即可。題中數據滿足下面條件：1≦F≦100，F≦V≦100，－50≦AIJ≦50，其中 AII 是花束 I 擺放在花瓶 J 中的美學值。輸入整數 F，V 和矩陣 (AIJ)，輸出最大美學值和每束花擺放在各個花瓶中的花瓶編號。
┌───┬───┬───┬───┬───┬───┐
│ │花瓶 1│花瓶 2 │花瓶 3│花瓶 4 │花瓶 5│
├───┼───┼───┼───┼───┼───┤
│杜鵑花│ 7 │ 23 │ -5 │ -24 │ 16 │
├───┼───┼───┼───┼───┼───┤
│秋海棠│ 5 │ 21 │ -4 │ 10 │ 23 │
├───┼───┼──┼─── ┼── ─┼───┤
│康乃馨│ -21 │ 5 │ -4 │ -20 │ 20 │
\───┴───┴───┴───┴───┴───┘
【輸入文件】
第一行包含兩個數：F，V。 隨後的 F 行中，每行包含 V 個整數，Aij 即為輸入文件中第（i+1 ）行中的第 j 個數
【輸出文件】
包含兩行：第一行是程序所產生擺放方式的美學值。第二行必須用 F 個數表示擺放方式，即該行的第 K 個數表示花束 K 所在的花瓶的編號。
【輸入樣例】
3 5
7 23 –5 –24 16
5 21 -4 10 23
-21 5 -4 -20 20
【輸出樣例】
53
2 4 5
【題目鏈接】
http://mail.bashu.cn:8080/JudgeOnline/showproblem?problem\_id=1597
【問題分析】
這個問題很奇怪題目中給定的條件是花瓶和花束，似乎是兩個沒有關聯的事物啊，但著兩個看似沒關聯的東西，卻有一點聯繫：不同的花放在不同的花瓶中產生不同的美學價值。
一般人的思維都是拿來花一個一個的放，假設要放第 i 束花時，把它放到哪裡好呢？
很容易想到一個貪心的策略：找到一個符合條件（第 i 束花要放在前 i-1 束花的後面）下的它放如後能產生最大的美學價值的花瓶放。但和容易舉出反例：
│ │花瓶 1│花瓶 2 │花瓶 3│
├───┼───┼───┼───|
│杜鵑花│ 1 │ 2 │ -5 |
├───┼───┼───┼─——|
│秋海棠│ 5 │ 10 │ 1 │
按照貪心策略是：杜鵑花放在 2 號瓶裡，秋海棠放在 3 號瓶裡，美學值：3
答案是： 杜鵑花放在 1 號瓶裡，秋海棠放在 2 號瓶裡，美學值：11
數據量很大搜索顯然不行。
那要是動態規劃，階段，狀態，決策有是什麼呢？
既然要拿來花束一個一個的放，我們就以花束劃分階段。設計一個狀態 opt [i,j] 表示將第 i 束花放在第 j 個花瓶中可使前 i 束花或得的最大美學價值，那麼決策就很容易想到了：將第 i 束花放在第 j 個瓶中，那麼第 i-1 束花只能放在前 j-1 個瓶裡，顯然我們要找到一個放在前 j-1 個瓶中的一個最大的美學價值在加上當前第 i 束放在第 j 個瓶中的美學價值就是 OPT [I，J] 的值。
顯然符合最優化原理和無後效性。
狀態轉移方程：
opt [i,j]=max {opt [i-1,k]}+a [i,j] (i<=k<=j-1) 為什麼是 iopt [i,j] then
begin
opt[i,j]:=opt[i-1,k];
path[i,j]:=k;
end;
inc(opt[i,j],a[i,j]);
end;
ans:=n;
for i:=n+1 to m do
if opt[n,i]>opt[n,ans]then ans:=i;
end;
procedure outputway(i,j);
begin
if i>0 then
begin
outputway(i-1,path[i,j]);
write(j,' ');
end;
end;
procedure print;
var
i;
begin
writeln(opt[n,ans]);
outputway(n,ans);
writeln;
end;
begin
init;
main;
print;
end.
例題 26 Divisibility 來源：ZJU2042
【問題描述】
Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions:
17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.
You are to write a program that will determine divisibility of sequence of integers.
譯題：
給出 N 個數，你可以在這 N 個數中任意地添加 + 號或 - 號，求出能不能使算出的結果被 K 整除。可以則打印「Divisible」，否則打印「Not divisible」
(1 <= N <= 10000, 2 <= K <= 100)
下面是一個例子：
有 4 個數，分別是 17 5 -21 15
17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
有 8 種添法，其中第二種求出的 - 14 能被 7 整除。
【輸入文件】
The first line of the input contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space.
The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.
注意第一個數是測試數據的組數，多組測試數據一起測。。
【輸出文件】
Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
注意：輸出每組結果之間有空格，最後一行無空格，格式不對不能 AC，我就是因為格式不對調了一上午。。。。
【輸入樣例】
2
4 7
17 5 -21 15
4 5
17 5 -21 15
【輸出樣例】
Divisible
Not divisible
【問題分析】
看到題目第一個反映就是枚舉中間添的運算符，算出值在 MOD K 如果有一個值 MOD K=0 則輸出「Divisible」。
時間複雜度是 O（2N-1）。
但是題目給出的數據量很大，這樣做效率太低了。
因為題目涉及 MOD 運算，要想簡化問題就需要知道一些基本的 MOD 運算性質：
A*B mod C=(A mod C*B mod C) mod C
(A+B) mod C=(A mod C+B mod C) mod C
有了這個性質，我們就可以把累加後求余轉化成求余後累加（我們把減法看作加負數以後分析只說加法）再求余。這樣我們的讀入數據就控制在了 1-K 到 K-1 的範圍內了。
我們要判斷的就是
所有結果的累加和 MOD K 是否為 0。簡記為:
（A+B）mod K=0 or (A+B) mod K0
如果我們按數的個數劃分階段，前 N-1 個數的運算結果 MOD K 看做 A，第 N 個數看作 B 就 OK 了。
於是我們想到了這樣的狀態：opt [i,j] 表示前 i 個數是否可以得到餘數為 J 的結果。
那麼狀態轉移方程就是
opt[i,(j-a[i] mod k )mod k]=opt[i-1,j] (opt[i-1,j]=true);
opt[i,(j+a[i] mod k) mod k]=opt[i-1,j] (opt[i-1,j]=true);
如果 opt [n,0]=true 就輸出『Divisible'
注意上面
【源代碼】
program P2042;
const
maxk=110;
maxn=10010;
var
a[0..maxn] of longint;
opt[1..2,-maxk..maxk] of boolean;
n,k,tim,ii;
vis[0..maxn] of boolean;
procedure init;
var
i;
begin
read(n,k);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j,p1,p2,p3;
begin
fillchar(opt,sizeof(opt),false);
fillchar(vis,sizeof(vis),false);
for i:=1 to n do
if a[i] mod k=0 then vis[i]:=true;
for i:=1 to n do
a[i]:=a[i] mod k;
opt[1,a[1]]:=true;
p1:=1;
p2:=2;
for i:=2 to n do
if not vis[i] then
begin
fillchar(opt[p2],sizeof(opt[p2]),false);
for j:=1-k to k-1 do
if opt[p1,j] then
begin
opt[p2,(j-a[i]) mod k]:=true;
opt[p2,(j+a[i]) mod k]:=true;
end;
p3:=p1;
p1:=p2;
p2:=p3;
end;
if opt[p1,0] then writeln('Divisible')
else writeln('Not divisible');
end;
begin
read(tim);
for ii:=1 to tim do
begin
if ii>1 then
writeln;
init;
main;
end;
end.
3. 多維狀態和動態規劃的優化
一般多維動態規劃的時，空間複雜度較高，所以我們要想辦法將其優化，我就把多維動態規劃和動態規劃的優化放到一起了……
多維動態規劃以三，四維最為常見，在多的也沒有太大的研究價值，其實多維動態規劃大多也就是上面的一維，和二維的加一些條件，或是在多進程動態規劃中要用到。當然除了這些特點外，狀態的表示也有一些共性。
三維：狀態 opt [i,j,k] 一般可表示下面的含義：
（1）二維狀態的基礎上加了某個條件，或其中一維變成兩個。
比如 opt [L,i] 表示起點為 I，長度為 L 的序列的最優值。opt [L,i,j] 就可表示起點是 i 和起點是 j，長度是 L 的兩個序列的最優值。
（2）I，J，K 組合表示一個正方形（（i,j）點為一角，邊長為 K）。
（3）I，J，K 組合表示一個等邊三角形（（i,j）點為一角，邊長為 K）。
四維：除了二維和三維加條件外，還可以用 i,j,k,t 組合來描述一個矩形，
（i,j）點和（k,t）點是兩個對頂點。
四維以上的一般都是前幾維加了條件了，這裡就不多說了。
動態規劃的優化：
動態規劃的優化往往需要較強的數學功底。
常見空間優化：
滾動數組，滾動數組在前面也提到過，其實很簡單，如果一個狀態的決策的步長為 N 就只保留以求出的最後 N（一般 N=1）個階段的狀態，因為當前狀態只和後 N 個階段中的狀態有關，再以前的已經利用過了，沒用了就可以替換掉了。具體實現是最好只讓下標滾動（這樣更省時間）。
X：=K1，K1：=K2，K2；=K3，K3：=X 這樣就實現了一個 N=3 的下標的滾動，在滾動完如果狀態是涉及累加，累乘類的操作要注意將當前要求的狀態初始化。
常見時間優化：利用一些數據結構（堆，並查集，HASH）降低查找複雜度。
時間空間雙重優化：改變狀態的表示法，降低狀態維數。
具體的多維動態規劃和動態規劃的優化，我們從題目裡體會吧！
3.1 矩陣問題
先看一道題
例題 27 蓋房子 來源：VIJOS P1057
【問題描述】
永恆の靈魂最近得到了面積為 n*m 的一大塊土地（高興 ING^_^），他想在這塊土地上建造一所房子，這個房子必須是正方形的。
但是，這塊土地並非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。這些瑕疵十分噁心，以至於根本不能在上面蓋一磚一瓦。
他希望找到一塊最大的正方形無瑕疵土地來蓋房子。
不過，這並不是什麼難題，永恆の靈魂在 10 分鐘內就輕鬆解決了這個問題。現在，您也來試試吧。
【輸入文件】
輸入文件第一行為兩個整數 n,m（1<=n,m<=1000），接下來 n 行，每行 m 個數字，用空格隔開。0 表示該塊土地有瑕疵，1 表示該塊土地完好。
【輸出文件】
一個整數，最大正方形的邊長。
【輸入樣例】
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
【輸出樣例】
2
【問題分析】
題目中說要求一個最大的符合條件的正方形，所以就想到判斷所有的正方形是否合法。
這個題目直觀的狀態表示法是 opt [i,j,k] 基類型是 boolean，判斷以（i,j）點為左上角（其實任意一個角都可以，依據個人習慣）, 長度為 K 的正方形是否合理，再找到一個 K 值最大的合法狀態就可以了（用 true 表示合理，false 表示不合理）。其實這就是遞推，（決策唯一）。
遞推式：
opt[i,j,k]=opt[i+1,j+1,k-1] and opt[i+1,j,k-1] and opt[i,j+1,k-1] and (a[i,j]=1)
時間複雜度：
狀態數 O（N3）* 轉移代價 O（1）= 總複雜度 O（N3）
空間複雜度：
O（N3）
由於空間複雜度和時間複雜度都太高，不能 AC，我們就的再想想怎麼優化？
顯然何以用滾動數組優化空間，但是時間複雜度仍然是 O（N3）。這就需要我們找另外一種簡單的狀態表示法來解了。
仔細分析這個題目，其實我們沒必要知道正方形的所有長度，只要知道以一個點為左上角的正方形的最大合理長度就可以了。
如果這個左上角是 0 那麼它的最大合理長度自然就是 0（不可能合理）。
如果這個左上角是 1 呢？
回顧上面的遞推式，我們考慮的是以它的右面，下面，右下這個三個方向的正方形是否合理，所以我們還是要考慮這三個方向。具體怎麼考慮呢？
如果這三個方向合理的最大邊長中一個最小的是 X，那麼它的最大合理邊長就是 X+1。為什麼呢？
看個例子：
0 1 1 1 1 1
1 1 1 1 1 1
0 1 0 1 1 0
1 1 0 1 1 1
上例中紅色的正方形，以（1,3）點為左上角，以（1，4），（2，3），（2，4）這三個點的最大合理邊長分別是 2，1，2。其中最小的是以（2，3）為左上角的正方形，最大合理邊長是 1。因為三個方向的最大合理邊長大於等於 1，所以三個方向上邊長為 1 的正方形是合理的，即上面低推式中:
opt [1,3,2]=opt [1,4,1] and opt [2,3,1] and opt [2,4,1] and (a [1,3]=1) = true 成立
這樣就把一個低推判定性問題轉化成最優化問題從而節省空間和時間。
具體實現：
設計一個狀態 opt [i,j] 表示以（i,j）為左上角的正方形的最大合理邊長。
狀態轉移方程：
min{opt[i+1,j],opt[i,j+1],opt[i+1,j+1]}+1 (a[i,j]=1)
opt[i,j]=0 (a[i,j]=0)
時間複雜度：狀態數 O（N2）* 轉移代價 O（1）= 總代價 O（N2）
空間複雜度：O（N2）
【源代碼】
program P1057;
const
maxn=1010;
var
opt,a[0..maxn,0..maxn] of longint;
n,m,ans;
procedure init;
var
i,j;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
for i:=n downto 1 do
for j:=m downto 1 do
if a[i,j]0 then
begin
opt[i,j]:=opt[i+1,j];
if opt[i,j+1]<opt[i,j] then
opt[i,j]:=opt[i,j+1];
if opt[i+1,j+1]ans then ans:=opt[i,j];
writeln(ans);
end;
begin
init;
main;
end.
3.2 多進程動態規劃
從字面上就可以看出，所謂多進程就是在原文題的基礎上要求將這個問題重複多次的總和最大。
具體怎麼做看個例題吧。
例題 28 方格取數 (fgqs.pas/c/cpp) 來源：NOIP2000 (提高組)
【問題描述】
設有 N*N 的方格圖 (N<=10, 我們將其中的某些方格中填入正整數，而其他的方格中則放入數字 0。如下圖所示（見樣例）：
某人從圖的左上角的 A 點出發，可以向下行走，也可以向右走，直到到達右下角的 B 點。在走過的路上，他可以取走方格中的數（取走後的方格中將變為數字 0）。
此人從 A 點到 B 點共走兩次，試找出 2 條這樣的路徑，使得取得的數之和為最大。
【輸入文件】
輸入的第一行為一個整數 N（表示 N*N 的方格圖），接下來的每行有三個整數，前兩個表示位置，第三個數為該位置上所放的數。一行單獨的 0 表示輸入結束。
【輸出文件】
只需輸出一個整數，表示 2 條路徑上取得的最大的和。
【輸入樣例】
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
【輸出樣例】
67
【問題分析】
這是一道很經典的多進程動態規劃題，如果只取一次，它的模型就是我們前面講的街道問題了，很簡單就可以實現。現在要求取兩次，怎麼辦呢？
一個自然的想法是：將前面的取過的數全賦成 0，然後在取一次，感覺挺對的，樣例也過了。
但這樣做是錯的，第一次取的顯然是最大值，但第二次取的未必次大，所以也許兩條非最大的路，也許比一條最大一條小一點的路更優。
看個例子：
0 0 2 0 3 0 0 0 2 0 3 0
0 0 2 0 0 0 0 0 2 0 0 0
0 0 2 0 2 0 0 0 2 0 2 0
0 0 0 0 2 0 0 0 0 0 2 0
0 0 0 0 2 0 0 0 0 0 2 0
0 0 2 0 2 0 0 0 2 0 2 0
圖 1 圖 2
如上圖，圖 1 是按找上訴思路求得的解。圖中紅色路線是第一求得的最大值，顯然圖 1 紅色和紫色兩條路徑不如圖 2 藍色和綠色兩條路徑大。
既然這樣做不行，我們還得回到動態規劃的本質來看代問題，我們在想想這個問題的狀態，對於走一次，走到矩陣的任意一個位置就是一個狀態，而要是走兩次，顯然走到矩陣的某個位置只是一個狀態的一部分，不能完整的描述整個狀態。那另一部分顯然就是第二次走到的位置了。如果我們把這兩部分合起來就是一個完整的狀態了。
於是，設計一個狀態 opt [i1,j1,i2,j2] 表示兩條路分別走到（i1,j1）點和（i2,j2）點時取到的最大值。顯然決策有 4 中（乘法原理一個點兩種 * 另一個點的兩中）
即（上，上）（上，左）（左，上）（左，左）上和左表示從哪個方向走到該點，當然要注意走到同行，同列，同點時的情況（因為要求路徑不重複）。
狀態轉移方程：
max(opt[i1-1,j1,i2-1,j2],opt[i1,j1-1,i2-1,j2])+a[i1,j1]+a[i2,j2] (1<=i1=i2<=n,1<=j1<=j2<=n)
max(opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1])
(1<=j1=j2<=n,1<=i1<=i2<=n)
opt[i,j]= max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2],
opt[i1,j1-1,i2,j2-2])+a[i1,j1]+a[i2,j2] (1<=i1,j1<=i2,j2<=n)
max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2],
opt[i1,j1-1,i2,j2-2])+a[i1,j1] (1<=i1=i2<=n,1<=j1=j2y then max:=x;
end;
procedure main;
var
i1,i2,j1,j2;
begin
for i1:=1 to n do
for j1:=1 to n do
for i2:=i1 to n do
for j2:=1 to j1 do
if (i1=i2) and (j1=j2) then
opt[i1,j1,i2,j2]:=opt[i1-1,j1,i2,j2-1]+a[i1,j1]
else if (i1=i2-1) and (j1=j2) then
opt[i1,j1,i2,j2]:=max(opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1])
+a[i1,j1]+a[i2,j2]
else if (i1=i2) and (j1=j2+1) then
opt[i1,j1,i2,j2]:=max(opt[i1-1,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2])
+a[i1,j1]+a[i2,j2]
else begin
opt[i1,j1,i2,j2]:=max(opt[i1-1,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2]);
opt[i1,j1,i2,j2]:=max(opt[i1,j1,i2,j2],opt[i1,j1-1,i2,j2-1]);
opt[i1,j1,i2,j2]:=max(opt[i1,j1,i2,j2],opt[i1,j1-1,i2-1,j2]);
inc(opt[i1,j1,i2,j2],a[i1,j1]+a[i2,j2]);
end;
end;
procedure print;
begin
writeln(opt[n,n,n,n]);
close(output);
end;
begin
init;
main;
print;
end.
如果這個題的數據範圍在大點就得優化了，怎麼優化這個程序呢？
上面說過對於時間空間都大的時候，首先想到的就是尋找特點，改變狀態的表示法，減少狀態的維數。
仔細分析我們發現，處於同行，同列的狀態，等價於另外一個點在對角線上的狀態。而這條對角線正是此題的階段。因為在狀態轉移的時候後面的哪個點總是從固定的一個方向轉移來的。也就是說我們只要對角先上的狀態就可以省掉那些同行同列的狀態了。
做過 N 皇的同學一定知道怎麼表示右上到左下的這幾條對角線，不知道的同學也沒關係，對於一個點（i,j）他對角右上角的點就是（i-1，j+1）所以可以看出這些點的和是定值，且值從 2 到 N*2。
這樣用三個變量就可以表示這兩個點了，於是設計狀態 opt [k,i1,i2] 表示處於階段 K 時走到 i1,i2 的兩條路徑所取得的數的最大和。
用上面的思維不難想出動態轉移方程：
max(opt[k-1,i1-1,i2-1],opt[k-1,i1-1,i2],opt[k-1,i1,i2-1],opt[k-1,i1,i2])+a[i1,k-i1]+a[i2,k-i2](1<=i1,i2<=n,2<=k<=n*2,i1i2)
otp[k,i1,i2]=opt[k-1,i1-1,i2]+a[i1,k-i1](1<=i1,i2<=n,2<=ky then max:=x;
end;
procedure main;
var
k,i1,i2,j1,j2,mid;
begin
for k:=2 to n*2 do
begin
for i1:=1 to n do
if (k-i1>0) and (k-i10) and (k-i2=1）子樹的最優解，決策會很多。以至於我們沒發寫出準確的狀態轉移方程。這就是我們為什麼要把多叉數轉化成二叉數的原因。（當然，如果問題是求所有子樹的和，就沒必要轉化了，如 URAL P1039 沒有上司的舞會）。
如果把多叉樹或森林轉化成二叉樹要注意，左兒子和根結點是父子關係，而右兒子在原問題中和跟結點是兄弟關係。（這個數據結構掌握紮實的應該能明白，不理解的就去看數據結構方面的知識）。
用鄰接矩陣存多叉樹，轉化成二叉樹的部分代碼（可能有語法錯誤）
G: 存圖，F [i] 表示第 i 個結點的兒子應該插入的位置
W：結點的值 BT：二叉樹
Procedure creat_tree(T);
Var
i;
Begin
for i:=1 to n do
Begin
for j:=1 to n do
If g[i,j] then
Begin
If F[i]=0 then
BT[i].L:=j
Else BT[F[i]].r:=j;
F[i]:=j;
End;
End;
End;
下面同過例題看一下樹型動態規劃的具體實現：
例題 29 加分二叉樹 (binary.pas/c/cpp) 來源：NOIP2003（提高組）
【問題描述】
設一個 n 個節點的二叉樹 tree 的中序遍歷為（l,2,3,…,n），其中數字 1,2,3,…,n 為節點編號。每個節點都有一個分數（均為正整數），記第 i 個節點的分數為 di，tree 及它的每個子樹都有一個加分，任一棵子樹 subtree（也包含 tree 本身）的加分計算方法如下：
subtree 的左子樹的加分 × subtree 的右子樹的加分＋subtree 的根的分數
若某個子樹為空，規定其加分為 1，葉子的加分就是葉節點本身的分數。不考慮它的空
子樹。
試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹 tree。要求輸出；
（1）tree 的最高加分
（2）tree 的前序遍歷
【輸入格式】
第 1 行：一個整數 n（n＜30），為節點個數。
第 2 行：n 個用空格隔開的整數，為每個節點的分數（分數＜100）。
【輸出格式】
第 1 行：一個整數，為最高加分（結果不會超過 4,000,000,000）。
第 2 行：n 個用空格隔開的整數，為該樹的前序遍歷。
【輸入樣例】
5
5 7 1 2 10
【輸出樣例】
145
3 1 2 4 5
【問題分析】
根據題目描述就可以看出是典型的樹型動態規劃，而且題目中已經給出了加分的求法：
subtree 的左子樹的加分 × subtree 的右子樹的加分＋subtree 的根的分數
這估計是最簡單的題目了。
但是有一點需要注意：我們應該怎麼建樹？
其實這個題不用建樹，這就需要我們對數據結構掌握的很紮實。
題目中說這個樹的中序遍歷是 1，2，3……N，我們要求的是樹的先序，這樣馬上就想到怎樣用中序和先序確定一棵樹。
枚舉樹根 i 那麼 1，2……i-1 就是它的左子樹中的結點，i+1……N 就是它右子樹中的結點。這樣一顆樹按這樣的低歸定義就構造出來了，（當然我們只要這個過程並不需要存儲這棵樹）。在構造過程中順便求出加分來，在一個序列裡不同的元素做根顯然加分不同，我們只要記錄一個最大的就可以了。
具體實現方法：
設計狀態 opt [L,r] 表示以 L 為起點，以 r 為終點的結點所組成的樹的最高加分，階段就是樹的層數。決策就是在這些結點中找一個結點做根使樹的加分最大，狀態轉移方程：
1 (L>r)
opt[L,r] = a[L] (L=r)
max{opt[L,i-1]*opt[i+1,r]+a[i]} (L<r,L<=ir then
begin
opt[L,r]:=1;
path[L,r]:=0;
end
else if L=r then
begin
opt[L,r]:=a[L];
path[L,r]:=L;
end
else begin
for i:=L to r do
begin
x:=TreeDp(L,i-1)*TreeDp(i+1,r)+a[i];
if x>opt[L,r] then
begin
opt[L,r]:=x;
path[L,r]:=i;
end;
end;
end;
end;
TreeDp:=opt[L,r];
end;
procedure print(L,r);
begin
if path[L,r]>0 then
begin
write(path[L,r],' ');
print(L,path[L,r]-1);
print(path[L,r]+1,r);
end;
end;
begin
init;
writeln(TreeDp(1,n));
print(1,n);
close(output);
end.
例題 30 A Binary Apple Tree 蘋果二叉樹 來源：URAL P1018
【問題描述】
設想蘋果樹很像二叉樹，每一枝都是生出兩個分支。我們用自然數來數這些枝和根那麼必須區分不同的枝（結點），假定樹根編號都是定為 1，並且所用的自然數為 1 到 N。N 為所有根和枝的總數。例如下圖的 N 為 5，它是有 4 條枝的樹。
2 5
\ /
3 4
\ /
1
當一棵樹太多枝條時，採摘蘋果是不方便的，這就是為什麼有些枝要剪掉的原因。現在我們關心的是，剪枝時，如何令到損失的蘋果最少。給定蘋果樹上每條枝的蘋果數目，及必須保留的樹枝的數目。你的任務是計算剪枝後，能保留多少蘋果。
【輸入文件】
首行為 N，Q (1 <= Q <= N, 1 < N <= 100), N 為一棵樹上的根和枝的編號總數，Q 為要保留的樹枝的數目。以下 N-1 行為每條樹枝的描述，用 3 個空格隔開的整數表示，前 2 個數為樹枝兩端的編號，第三個數為該枝上的蘋果數。假設每條枝上的蘋果數不超過 3000 個。
【輸出文件】
輸出能保留的蘋果數。（剪枝時，千萬不要連根拔起哦）
【輸入樣例】
5 2
1 3 1
1 4 10
2 3 20
3 5 20
【輸出樣例】
21
【問題分析】
和上一道題一樣，題目描述就很明確的說是關於樹的題目，在加上是求最優值，和上一道題不同的是，這個題目邊有值，並非點有值，還有一個不同點就是這個題需要建樹。
建樹是要注意，給每個結點增加一個域：SUM 用來存以它為根的樹中的邊的數目。
其實樹型動態規劃是最好分析的，因為樹這種數據結構本來就符合遞歸定義，這樣的話子問題很好找，顯然這個問題的子問題就是一棵樹要保留 M 個枝分三種情況：
剪掉左子樹：讓右子樹保留 M-1 個枝可保留最多的蘋果數 + 連接右子樹的枝上的蘋果數
剪掉右子樹：讓左子樹保留 M-1 個枝可保留最多的蘋果數 + 連接左子樹的枝上的蘋果數
都不剪掉： 讓左子樹保留 i 個枝，讓右子樹保留 M-2-i 個枝可保留最多的蘋果數 + 連接右子樹的枝上的蘋果數 + 連接左子樹的枝上的蘋果數
顯然邊界條件就是如果要保留的枝子數比當前的子樹的枝多，或著一個樹要保留 0 個枝子，則結果就是 0。
應為一顆樹中根接點是對子樹的完美總結，所以滿足最優化原理。
沒次求解只和子樹有關所以也滿足無後效性，可見用動態規劃做是正確的。
設計一個狀態 opt [num,i] 表示要讓結點編號為 i 的樹保留 num 個枝可得到的最優解。
狀態轉移方程：
opt[num,i]=max{opt[num-1,BT[i].L]+T[i,BT[i].L],opt[num-1,BT[i].r]+T[i,BT[i].r],opt[k,BT[i].L]+opt[num-2-k,BT[i].r]+T[i,BT[i].L]+T[i,BT[i].r]}
(0<=k0) and (not vis[j]) then
begin
creat_tree(j);
BT[i].L:=Bt[i].r;
Bt[i].r:=j;
inc(Bt[i].sum,BT[j].sum+1);
end;
end;
Function max(x,y);
begin
max:=y;
if x>y then max:=x;
end;
Function F(num,i);
var
k;
begin
if opt[num,i]BT[i].sum) or (num=0) then opt[num,i]:=0
else begin
opt[num,i]:=F(num-1,BT[i].L)+T[i,BT[i].L];
opt[num,i]:=max(opt[num,i],F(num-1,BT[i].r)+T[i,BT[i].r]);
for k:=0 to num-2 do
opt[num,i]:=max(opt[num,i],F(k,BT[i].L)+F(num-2-k,BT[i].r)
+T[i,BT[i].L]+T[i,BT[i].r]);
end;
end;
F:=opt[num,i];
end;
begin
init;
creat_tree(1);
fillchar(opt,sizeof(opt),200);
writeln(F(m,1));
close(output);
end.
例題 31 選課 來源：VIJOS P1180
【問題描述】
學校實行學分制。每門的必修課都有固定的學分，同時還必須獲得相應的選修課程學分。學校開設了 N（N<300）門的選修課程，每個學生可選課程的數量 M 是給定的。學生選修了這 M 門課並考核通過就能獲得相應的學分。
在選修課程中，有些課程可以直接選修，有些課程需要一定的基礎知識，必須在選了其它的一些課程的基礎上才能選修。例如《Frontpage》必須在選修了《Windows 操作基礎》之後才能選修。我們稱《Windows 操作基礎》是《Frontpage》的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。每門課都有一個課號，依次為 1，2，3，…。例如:
表中 1 是 2 的先修課，2 是 3、4 的先修課。如果要選 3，那麼 1 和 2 都一定已被選修過。 你的任務是為自己確定一個選課方案，使得你能得到的學分最多，並且必須滿足先修課優先的原則。假定課程之間不存在時間上的衝突。
【輸入文件】
輸入文件的第一行包括兩個整數 N、M（中間用一個空格隔開）其中 1≦N≦300,1≦M≦N。
以下 N 行每行代表一門課。課號依次為 1，2，…，N。每行有兩個數（用一個空格隔開），第一個數為這門課先修課的課號（若不存在先修課則該項為 0），第二個數為這門課的學分。學分是不超過 10 的正整數。
【輸出文件】
輸出文件只有一個數，實際所選課程的學分總數。
【輸入樣例】
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
【輸出樣例】
13
【問題分析】
事先說明題目描述有個漏洞，應該是二個以上的課程可能有同一個先修課。
換句話講，一個課程可能是多個課程的先修課，可是一個課最多只有一個先修課。這樣的描述好像和我們以前學過的一種數據結構的描述一樣。
你想對了，就是樹。
因為是建立在樹這種數據結構上的最優化問題，我們自然想到了樹型動態規劃。想到樹型動態規劃，那麼第一步就是想這課樹是否是二叉樹，如果不是，是否需要轉化呢？
顯然這個問題不是二叉樹，有應為問題是在多個課程中選 M 個，也就是說是樹中一棵或多棵子樹的最優解，這樣問題就需要轉化成二叉樹了。注意題目中說一個課程沒有先修課是 0，也就是說這課樹的根是 0。
把數據結構確定了以後就要想動態規劃的三要素了。
樹型動態規劃階段的具有共性：樹的層數，
狀態是結點，但是只描述結點顯然不夠，需要在加一個參數。於是我們想到設計一個狀態 opt [i,j] 表示以 i 為跟的樹，選 j 個課程可獲得的最優解。
因為樹是以 0 為根的而 0 又必須要選所以問題的解不是 opt [0,m] 而是 opt [0,m+1]。
決策是什麼呢？
對於二叉樹我在設計決策時習慣分類討論這樣結構清晰。
這棵樹只有左子樹：
要選左子樹中的課程，那麼根結點一定要選，所以決策就是在左子樹中選 j-1 個課程，在加上選根結點可獲得的分數。
這棵樹只有右子樹：
因為右子樹和根在原問題中是兄弟關係，所以選右子樹中的課程未必要選根，這樣決策就有兩條：（1）在右子樹中選 j 個的最優值。（2）在右子樹中選 j-1 個的最優值加上選根結點可獲得的分數。
都有：
這種情況的決策很容易想到，從左子樹中選 k-1 個，從右子樹中選 j-k 個的最優值加上根結點可獲得的分數。
但要注意，當 K=1 也就是左子樹選 0 個時，根結點可以不選，右子樹可以選 j 個而不是 j-1 個；當然根結點也可以選，選了根結點右子樹就得選 j-1 個了。
針對不同情況寫出狀態轉移方程：
max (opt [t [i].L,j-1]+t [i].data) （只有左子樹）
opt [i,j] = max (opt [t [i].r,j-1]+t [i].data, opt [t [i].r,j]) （只有右子樹）
max (opt [t [i].L,k-1]+opt [t [i].r,j-k]+t [i].data,opt [t [i].r,j])（都有）
(1<=ky then max:=x;
end;
function TreeDp(i,j);
var
k;
begin
if opt[i,j]<0 then
begin
if (T[i].L<0) and (T[i].r<0) then
begin
if j1 then opt[i,j]:=0
else opt[i,j]:=T[i].data;
end
else if (T[i].L>=0) and (T[i].r<0) then
opt[i,j]:=max(opt[i,j],TreeDp(T[i].L,j-1)+T[i].data)
else if (T[i].L=0) then
begin
opt[i,j]:=max(opt[i,j],TreeDp(T[i].r,j));
opt[i,j]:=max(opt[i,j],TreeDp(T[i].r,j-1)+T[i].data);
end
else begin
opt[i,j]:=max(opt[i,j],TreeDp(T[i].r,j));
for k:=1 to j do
opt[i,j]:=max(opt[i,j],TreeDp(T[i].L,k-1)+
TreeDp(T[i].r,j-k)+T[i].data);
end;
end;
TreeDp:=opt[i,j];
end;
begin
init;
writeln(TreeDp(0,m+1));
end.