1、1.資源問題1-機器分配問題FI,j:=max(fi-1,k+wi,j-k)2.資源問題2-01背包問題FI,j:=max(fi-1,j-vi+wi,fi-1,j); 3.線性動態規劃1-樸素最長非降子序列Fi:=maxfj+14.剖分問題1-石子合并Fi,j:=min(fi,k+fk+1,j+sumi,j);5.剖分問題2-多邊形剖分FI,j:=min(fi,k+fk,j+ak*aj*ai);6.剖分問題3-乘積最大fi,j:=max(fk,j-1*multk,i);7.資源問題3 -系統可靠性(完全背包)Fi,j:=maxfi-1,j-ci*k*PI,x8.貪心的動態規劃1-快餐問題 Fi

2、,j表示前i條生產線生產j個漢堡,k個薯條所能生產的最多飲料, 則最多套餐ans:=minj div a,k div b,fI,j,k div cFi,j,k:=maxfi-1,j,k+(Ti-(j-j)*p1-(k-k)*p2) div p3 時間復雜度 O(10*1004) 9.貪心的動態規劃2-過河 fi=minf(i-k) (not stonei) f(i-k)+1 (stonei); +貪心壓縮狀態10.剖分問題4-多邊形-討論的動態規劃Fi,j:=max正正 fI,k*fk+1,j; 負負 gI,k*fk+1,j; 正負 gI,k*fk+1,j; 負正 fI,k*gk+1,j; g

3、為min11.樹型動態規劃1-加分二叉樹 (從兩側到根結點模型)FI,j:=maxfI,k-1*fk+1,j+ck12.樹型動態規劃2-選課 (多叉樹轉二叉樹,自頂向下模型)FI,j表示以i為根節點選j門功課得到的最大學分fi,j:=maxfti.l,k+fti.r,j-k-1+ci13.計數問題1-砝碼稱重const w:array1.n of shortint=(1，2，3，5，10，20)；/不同砝碼的重量var a:array 1.n of integer;/不同砝碼的個數f0:=1; 總重量個數(Ans)f1:=0; 第一種重量0;ff0+1=fj+k*wj;(1=i=n; 1=j=

4、f0; 1=k=ai;)14.遞推天地1-核電站問題f-1:=1; f0:=1; fi:=2*fi-1-fi-1-m 15.遞推天地2-數的劃分fi,j:=fi-j,j+fi-1,j-1;16.最大子矩陣1-一最大01子矩陣fi,j:=min(fi-1,j,vi,j-1,vi-1,j-1)+1; ans:=maxvalue(f); 17.判定性問題1-能否被4整除g1,0:=true; g1,1:=false; g1,2:=false; g1,3:=false;gi,j:=gi-1,k and (k+ai,p) mod 4 = j) 18.判定性問題2-能否被k整除fI,jni mod k:=

5、fi-1,j; -k=j=k; 1=i0,j0,xi=yj);maxfi,j-1+fi-1,j (i0,j0,xiyj);let(nm); (n=length(a); m:=length(b);for i:= 1 to n do begin x:=-1; p:=1; for j:= 1 to m do if ai=bj then begin x:=p; while flagj,x and (fj,xai) do inc(x); p:=x; fj,x:=ai; flagj,x:=true; end else if (x-1) and flagj-1,x and (not flagj,x) or

6、(fj-1,xfj,x) then begin fj,x:=fj-1,x; flagj,x:=true; end else x:=-1; end; ok:=false; for i:= m downto 1 do if flagm,i then begin writeln(i); ok:=true; break; end;if not ok then writeln(0);22.最大子矩陣2-最大帶權01子矩陣O(n2*m)枚舉行的起始，壓縮進數列，求最大字段和，遇0則清零fi:=max(fi-1+ai,ai) readln(n,m); for i:= 1 to n do for j:= 1

7、to m do read(ai,j); ans:=-maxlongint; for i:= 1 to n do begin fillchar(b,sizeof(b),0); fillchar(u,sizeof(u),0); for j:= i to n do begin max:=0; for k:= 1 to m do begin if (aj,k0) and (not uk) then begin inc(bk,aj,k); inc(max,bk) end else begin max:=0; uk:=true; end; if maxans then ans:=max; end; end

8、; end;23. 資源問題4-裝箱問題(判定性01背包)fj:=(fj or fj-vi);注:這里將數字三角形的意義擴大凡狀態轉移為圖形,跟其上面階段和前面狀態有關都叫數字三角形:)24.數字三角形1-樸素數字三角形fi,j:=max(fi+1,j+aI,j,fi+1,j+1+ai,j); 25.數字三角形2-晴天小豬歷險記之Hill同一階段上暴力動態規劃ifi,j:=min(fi,j-1,fI,j+1,fi-1,j,fi-1,j-1)+ai,j26.雙向動態規劃1數字三角形3-小胖辦證fi,j:=max(fi-1,j+ai,j,fi,j-1+ai,j,fi,j+1+ai,j)27. 數字

9、三角形4-過河卒/邊界初始化fi,j:=fi-1,j+fi,j-1;28.數字三角形5-樸素的打磚塊fi,j,k:=max(fi-1,j-k,p+sumi,k,fi,j,k);29.數字三角形6-優化的打磚塊fI,j,k:=maxgi-1,j-k,k-1+sumI,k30.線性動態規劃3-打鼴鼠fi:=fj+1;(abs(xi-xj)+abs(yi-yj)=3)39遞推天地9-Catalan數列一般形式1,1,2,5,14,42,132fn:=C(2k,k) div (k+1);40遞推天地10-彩燈布置排列組合中的環形染色問題fn:=fn-1*(m-2)+fn-2*(m-1); (f1:=m

10、; f2:=m(m-1);41線性動態規劃4-找數線性掃描 sum:=fi+gj; (if sum=Aim then getout; if sumAim then inc(i) else inc(j);) 42線性動態規劃5-隱形的翅膀min:=minabs(wi/wj-gold);if wi/wjl) then exit(WQ) else getS:=(l mod n)*k2*sqr(l div n+1)+ (n-l mod n)*k2*sqr(l div n)+ k1*sqr(l);end;if x+S(x,k)=fi,q,p then break else fi,q,p:=x+S(x,k

11、);inc(k);計數問題2-隕石的秘密（排列組合中的計數問題）Ansl1,l2,l3,D:=fl1+1,l2,l3,D+1-fl1+1,l2,l3,D;Fl1,l2,l3,D:=Sigma(fo,p,q,d-1*fl1-o,l2-p,l3-q,d);線性動態規劃-合唱隊形兩次Fi:=maxfj+1枚舉中央結點資源問題-明明的預算方案：加花的動態規劃fi,j:=max(fi,j,fl,j-vi-vfbi-vfai+vi*pi+vfbi*pfbi+vfai*pfai);資源問題-化工場裝箱員樹形動態規劃-聚會的快樂fi,2:=max(fi,0,fi,1);fi,1:=sigma(fti.son,

12、0);fi,0:=sigma(fti.son,3);樹形動態規劃-皇宮看守fi,2:=max(fi,0,fi,1);fi,1:=sigma(fti.son,0);fi,0:=sigma(fti.son,3);遞推天地-盒子與球fi,1:=1;fi,j:=j*(fi-1,j-1+fi-1,j);雙重動態規劃-有限的基因序列fi:=minfj+1gc,i,j:=(ga,i,j and gb,i,j) or (gc,i,j)最大子矩陣問題-居住空間 fi,j,k:=min(min(min(fi-1,j,k,fi,j-1,k), min(fi,j,k-1,fi-1,j-1,k), min(min(fi

13、-1,j,k-1,fi,j-1,k-1), fi-1,j-1,k-1)+1;線性動態規劃-日程安排fi:=maxfj+PI; (ejsi)遞推天地-組合數CI,j:=Ci-1,j+CI-1,j-1CI,0:=1樹形動態規劃-有向樹k中值問題FI,r,k:=maxmaxfli,I,j+fri,I,k-j-1,ffli,r,j+fri,r,k-j+wI,r樹形動態規劃-CTSC 2001選課FI,j:=wi(if iP)+fli,k+fri,m-k(0km)(if li0)線性動態規劃-多重歷史fi,j:=sigmafi-k,j-1(if checked)背包問題(+-1背包問題+回溯)-CEOI

14、1998 Substractfi,j:=fi-1,j-ai or fi-1,j+ai線性動態規劃(字符串)-NOI 2000 古城之謎fi,1,1:=minfi+length(s),2,1, fi+length(s),1,1+1fi,1,2:=minfi+length(s),1,2+wordss,fi+length(s),1,2+wordss線性動態規劃-最少單詞個數fi,j:=maxfI,j,fu-1,j-1+l線型動態規劃-APIO2007 數據備份狀態壓縮剪掉每個階段j前j*2個狀態和j*2+200后的狀態貪心動態規劃fi:=min(gi-2+si,fi-1);樹形動態規劃-APIO20

15、07 風鈴fi:=fl+fr+1 (if clcr)gi:=1(dldr) 0(dl=dr)gl=gr=1 then Halt;地圖動態規劃-NOI 2005 adv19910Ft,i,j:=maxft-1,i-dxdt,j-dydk+1,ft-1,i,j;地圖動態規劃-優化的NOI 2005 adv19910Fk,i,j:=maxfk-1,i,p+1 j-bk=p=p=l, 1=q=p;地圖動態規劃-vijos某題FI,j:=min(fi-1,j-1,fI,j-1,fi-1,j);最大子矩陣問題-最大字段和問題fi:=max(fi-1+bi,bi); f1:=b1最大子矩陣問題-最大子立方體

16、問題枚舉一組邊i的起始，壓縮進矩陣 BI,j+=ax,I,j枚舉另外一組邊的其實，做最大子矩陣括號序列-線型動態規劃fI,j:=min(fI,j,fi+1,j-1(sisj=”()”or(”),fI+1,j+1+1 (sj=”(”or” , fI,j-1+1(sj=”)”or” )棋盤切割-線型動態規劃fk,x1,y1,x2,y2=minminfk-1,x1,y1,a,y2+sa+1,y1,x2,y2,fk-1,a+1,y1,x2,y2+sx1,y1,a,y2min概率動態規劃-聰聰和可可(NOI2005)x:=ppi,j,jfI,j:=(fx,bj,k+fx,j)/(lj+1)+1fI,i=

17、0fx,j=1概率動態規劃-血緣關系 我們正在研究妖怪家族的血緣關系。每個妖怪都有相同數量的基因，但是不同的妖怪的基因可能是不同的。我們希望知道任意給定的兩個妖怪之間究竟有多少相同的基因。由于基因數量相當龐大，直接檢測是行不通的。但是，我們知道妖怪家族的家譜，所以我們可以根據家譜來估算兩個妖怪之間相同基因的數量。 妖怪之間的基因繼承關系相當簡單：如果妖怪C是妖怪A和B的孩子，則C的任意一個基因只能是繼承A或B的基因，繼承A或B的概率各占50。所有基因可認為是相互獨立的，每個基因的繼承關系不受別的基因影響。 現在，我們來定義兩個妖怪X和Y的基因相似程度。例如，有一個家族，這個家族中有兩個毫無關系

18、(沒有相同基因)的妖怪A和B，及它們的孩子C和D。那么C和D相似程度是多少呢？因為C和D的基因都來自A和B，從概率來說，各占50。所以，依概率計算C和D平均有50的相同基因，C和D的基因相似程度為50。需要注意的是，如果A和B之間存在相同基因的話，C和D的基因相似程度就不再是50了。 你的任務是寫一個程序，對于給定的家譜以及成對出現的妖怪，計算它們之間的基因相似程度。FA, B=(fA0, B+PA1, B)/2fI,i=1fI,j=0(I,j無相同基因)線性動態規劃-決斗FI,j=(fI,j and fk,j) and (eI,k or ej,k),ikNb則標0否則標1，用二進制狀態壓縮進

19、k中，在這種情況下的最小花費FI,j,k:=minfl,u,k and (si(i-1)+w1,fr,j-u,k and(si(i-1)樹形動態規劃-IOI2005 河流Fi:=max記憶化搜索-Vijos某題,忘了Fpre,h,m:=sigmaSDP(I,h+1,M+i) (pre=i=M1)狀態壓縮動態規劃-APIO 2007 動物園fI,k:=fi-1,k and not (1=0 then Min(fi,j,fi-1,j-k+time(i,k);背包問題- USACO Raucous Rockers多個背包，不可以重復放物品，但放物品的順序有限制。 FI,j,k表示決策到第i個物品、第

20、j個背包，此背包花費了k的空間。fI,j,k:=max(fI-1,j,k,fI-1,j,k-ti+pi,fi-1,j-1,maxtime-ti) 多進程動態規劃-巡游加拿大（IOI95、USACO）di,j=maxdk,j+1(ak,i & jki),dj,k+1(aI,j & (kj分析狀態(i,j)，它可能是(k,j)(jki)中k到達i得到（方式1），也可能是(j,k)(kj)中k超過j到達i得到（方式2）。但它不能是(i,k)(kj)中k到達j得到，因為這樣可能會出現重復路徑。即使不會出現重復路徑，那么它由(j,k)通過方式2同樣可以得到，所以不會遺漏解 時間復雜度O(n3) 動態規劃-ZOJ cheesefi,j:=fi-kk*zlu,1,j-kk*zlu,2+ai-kk*zlu,1,j-kk*zlu,2動態規劃-NOI 2004 berry 線性FI,1:=siFI,j:=maxminsi-sl-1,fl-1,j-1 (2jk, jli)動態規劃-NOI 2004 berry 完全無向圖FI,j:=fi-1,j or (jwi) and (fi-1,j-wi)動態規劃-石子合并 四邊形不等式優化mi,j=maxmi+1,j, mi,j-1+ti,j 動態規劃-CEOI 2005