壓縮動態規劃

㈠ noip中的最常用的演算法

沒有哪個更重要，要因題而異的。

DP方程：
1. 資源問題1

-----機器分配問題

F[I,j]:=max(f[i-1,k]+w[i,j-k])

2. 資源問題2

------01背包問題

F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);

3. 線性動態規劃1

-----樸素最長非降子序列

F[i]:=max{f[j]+1}

4. 剖分問題1

-----石子合並

F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);

5. 剖分問題2

-----多邊形剖分

F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);

6. 剖分問題3

------乘積最大

f[i,j]:=max(f[k,j-1]*mult[k,i]);

7. 資源問題3

-----系統可靠性(完全背包)

F[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]}

8. 貪心的動態規劃1

-----快餐問題

F[i,j]表示前i條生產線生產j個漢堡,k個薯條所能生產的最多飲料,

則最多套餐ans:=min{j div a,k div b,f[I,j,k] div c}

F[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2) div p3}

時間復雜度 O(10*100^4)

9. 貪心的動態規劃2

-----過河 f[i]=min{{f(i-k)} (not stone[i])

{f(i-k)}+1} (stone[i]); +貪心壓縮狀態

10. 剖分問題4

-----多邊形-討論的動態規劃

F[i,j]:=max{正正 f[I,k]*f[k+1,j];

負負 g[I,k]*f[k+1,j];

正負 g[I,k]*f[k+1,j];

負正 f[I,k]*g[k+1,j];} g為min

11. 樹型動態規劃1

-----加分二叉樹 (從兩側到根結點模型)

F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}

12. 樹型動態規劃2

-----選課 (多叉樹轉二叉樹,自頂向下模型)

F[I,j]表示以i為根節點選j門功課得到的最大學分

f[i,j]:=max{f[t[i].l,k]+f[t[i].r,j-k-1]+c[i]}

13. 計數問題1

-----砝碼稱重

const w:array[1..n] of shortint=(1，2，3，5，10，20)；

//不同砝碼的重量

var a:array [1..n] of integer;

//不同砝碼的個數

f[0]:=1; 總重量個數(Ans)

f[1]:=0; 第一種重量0;

f[f[0]+1]=f[j]+k*w[j];

(1<=i<=n; 1<=j<=f[0]; 1<=k<=a[i];)

14. 遞推天地1

------核電站問題

f[-1]:=1; f[0]:=1;

f[i]:=2*f[i-1]-f[i-1-m]

15. 遞推天地2

------數的劃分

f[i,j]:=f[i-j,j]+f[i-1,j-1];

16. 最大子矩陣1

-----一最大01子矩陣

f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;

ans:=maxvalue(f);

17. 判定性問題1

-----能否被4整除

g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false;

g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)

18. 判定性問題2

-----能否被k整除

f[I,j±n[i] mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n

20. 線型動態規劃2

-----方塊消除游戲

f[i,i-1,0]:=0

f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),

f[i,p,k+len[j]]+f[p+1,j-1,0]}

ans:=f[1,m,0]

21. 線型動態規劃3

-----最長公共子串，LCS問題

f[i,j]={0 (i=0)&(j=0);

f[i-1,j-1]+1 (i>0,j>0,x[i]=y[j]);

max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x[i]<>y[j]);

let(n>m); (n=length(a); m:=length(b));

for i:= 1 to n do

begin

x:=-1; p:=1;

for j:= 1 to m do

if a[i]=b[j] then

begin

x:=p;

while flag[j,x] and (f[j,x]<a[i]) do inc(x);

p:=x;

f[j,x]:=a[i];

flag[j,x]:=true;

end

else

if (x<>-1) and flag[j-1,x] and ((not flag[j,x]) or (f[j-1,x]<f[j,x])) then

begin

f[j,x]:=f[j-1,x];

flag[j,x]:=true;

end else x:=-1;

end;

ok:=false;

for i:= m downto 1 do

if flag[m,i] then begin writeln(i); ok:=true; break; end;

if not ok then writeln(0);

22. 最大子矩陣2

-----最大帶權01子矩陣O(n^2*m)

枚舉行的起始，壓縮進數列，求最大欄位和，遇0則清零

f[i]:=max(f[i-1]+a[i],a[i])

readln(n,m);

for i:= 1 to n do for j:= 1 to m do read(a[i,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 (a[j,k]<>0) and (not u[k]) then

begin

inc(b[k],a[j,k]);

inc(max,b[k])

end

else

begin

max:=0;

u[k]:=true;

end;

if max>ans then ans:=max;

end;

end;

end;

23. 資源問題4

-----裝箱問題(判定性01背包)

f[j]:=(f[j] or f[j-v[i]]);

注: 這里將數字三角形的意義擴大

凡狀態轉移為圖形,跟其上面階段和前面狀態有關都叫數字三角形:)

24. 數字三角形1

-----樸素の數字三角形

f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);

25. 數字三角形2

-----晴天小豬歷險記之Hill

同一階段上暴力動態規劃

if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j]

26. 雙向動態規劃1

數字三角形3

-----小胖辦證

f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])

27. 數字三角形4

-----過河卒

//邊界初始化

f[i,j]:=f[i-1,j]+f[i,j-1];

28. 數字三角形5

-----樸素的打磚塊

f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);

29. 數字三角形6

-----優化的打磚塊

f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]}

30. 線性動態規劃3

-----打鼴鼠』

f[i]:=f[j]+1;(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])

31. 樹形動態規劃3

-----貪吃的九頭龍

32. 狀態壓縮動態規劃1

-----炮兵陣地

Max(f[Q*(r+1)+k],g[j]+num[k])

If (map[i] and plan[k]=0) and

((plan[P] or plan[q]) and plan[k]=0)

33. 遞推天地3

-----情書抄寫員

f[i]:=f[i-1]+k*f[i-2]

34. 遞推天地4

-----錯位排列

f[i]:=(i-1)(f[i-2]+f[i-1]);

f[n]:=n*f[n-1]+(-1)^(n-2);

35. 遞推天地5

-----直線分平面最大區域數

f[n]:=f[n-1]+n

:=n*(n+1) div 2 + 1;

36. 遞推天地6

-----折線分平面最大區域數

f[n]:=(n-1)(2*n-1)+2*n;

37. 遞推天地7

-----封閉曲線分平面最大區域數

f[n]:=f[n-1]+2*(n-1)

:=sqr(n)-n+2;

38 遞推天地8

-----凸多邊形分三角形方法數

f[n]:=C(2*n-2,n-1) div n;

對於k邊形

f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3)

39 遞推天地9

-----Catalan數列一般形式

1,1,2,5,14,42,132

f[n]:=C(2k,k) div (k+1);

40 遞推天地10

-----彩燈布置

排列組合中的環形染色問題

f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); (f[1]:=m; f[2]:=m(m-1);

41 線性動態規劃4

-----找數

線性掃描

sum:=f[i]+g[j];

(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);)

42 線性動態規劃5

-----隱形的翅膀

min:=min{abs(w[i]/w[j]-gold)};

if w[i]/w[j]<gold then inc(i) else inc(j);

43 剖分問題5

-----最大獎勵

f[i]:=max(f[i],f[j]+(sum[j]-sum[i])*i-t

44 最短路1

-----Floyd

f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);

ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];

45 剖分問題6

-----小H的小屋

F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);

function GetS(l,n:longint):extended;

begin

if (n=0) or (n>l) 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)>=f[i,q,p] then break else f[i,q,p]:=x+S(x,k);inc(k);

46 計數問題2

-----隕石的秘密（排列組合中的計數問題）

Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];

F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);

47 線性動態規劃

------合唱隊形

兩次F[i]:=max{f[j]+1}＋枚舉中央結點

48 資源問題

------明明的預算方案：加花的動態規劃

f[i,j]:=max(f[i,j],f[l,j-v[i]-v[fb[i]]-v[fa[i]]]+v[i]*p[i]+v[fb[i]]*p[fb[i]]+v[fa[i]]*p[fa[i]]);

49 資源問題

-----化工場裝箱員

50 樹形動態規劃

-----聚會的快樂

f[i,2]:=max(f[i,0],f[i,1]);

f[i,1]:=sigma(f[t[i]^.son,0]);

f[i,0]:=sigma(f[t[i]^.son,3]);

51 樹形動態規劃

-----皇宮看守

f[i,2]:=max(f[i,0],f[i,1]);

f[i,1]:=sigma(f[t[i]^.son,0]);

f[i,0]:=sigma(f[t[i]^.son,3]);

52 遞推天地

-----盒子與球

f[i,1]:=1;

f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]);

53 雙重動態規劃

-----有限的基因序列

f[i]:=min{f[j]+1}

g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j])

54 最大子矩陣問題

-----居住空間

f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]),

min(f[i,j,k-1],f[i-1,j-1,k])),

min(min(f[i-1,j,k-1],f[i,j-1,k-1]),

f[i-1,j-1,k-1]))+1;

55 線性動態規劃

------日程安排

f[i]:=max{f[j]}+P[I]; (e[j]<s[i])

56 遞推天地

------組合數

C[I,j]:=C[i-1,j]+C[I-1,j-1]
C[I,0]:=1

57 樹形動態規劃

-----有向樹k中值問題

F[I,r,k]:=max{max{f[l[i],I,j]+f[r[i],I,k-j-1]},f[f[l[i],r,j]+f[r[i],r,k-j]+w[I,r]]}

58 樹形動態規劃

-----CTSC 2001選課

F[I,j]:=w[i](if i∈P)+f[l[i],k]+f[r[i],m-k](0≤k≤m)(if l[i]<>0)

59 線性動態規劃

-----多重歷史

f[i,j]:=sigma{f[i-k,j-1]}(if checked)

60 背包問題(+-1背包問題+回溯)
-----CEOI1998 Substract

f[i,j]:=f[i-1,j-a[i]] or f[i-1,j+a[i]]

61 線性動態規劃(字元串)

-----NOI 2000 古城之謎

f[i,1,1]:=min{f[i+length(s),2,1], f[i+length(s),1,1]+1} f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+words[s]}

62 線性動態規劃

-----最少單詞個數

f[i,j]:=max{f[I,j],f[u-1,j-1]+l}

63 線型動態規劃

-----APIO2007 數據備份

狀態壓縮＋剪掉每個階段j前j*2個狀態和j*2+200後的狀態貪心動態規劃

f[i]:=min(g[i-2]+s[i],f[i-1]);

64 樹形動態規劃

-----APIO2007 風鈴

f[i]:=f[l]+f[r]+{1 (if c[l]<c[r])}

g[i]:=1(d[l]<>d[r]) 0(d[l]=d[r])

g[l]=g[r]=1 then Halt;

65 地圖動態規劃

-----NOI 2005 adv19910

F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];

66 地圖動態規劃

-----優化的NOI 2005 adv19910

F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;

67 目標動態規劃

-----CEOI98 subtra

F[I,j]:=f[I-1,j+a[i]] or f[i-1,j-a[i]]

68 目標動態規劃

----- Vijos 1037搭建雙塔問題

F[value,delta]:=g[value+a[i],delta+a[i]] or g[value,delta-a[i]]

69 樹形動態規劃

-----有線電視網

f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j])

leaves[i]>=p>=l, 1<=q<=p;

70 地圖動態規劃

-----vijos某題

F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]);

71 最大子矩陣問題

-----最大欄位和問題

f[i]:=max(f[i-1]+b[i],b[i]); f[1]:=b[1]

72 最大子矩陣問題

-----最大子立方體問題

枚舉一組邊i的起始，壓縮進矩陣 B[I,j]+=a[x,I,j]

枚舉另外一組邊的其實，做最大子矩陣

73 括弧序列

-----線型動態規劃

f[I,j]:=min(f[I,j],f[i+1,j-1](s[i]s[j]=」()」or(」[]」)),

f[I+1,j+1]+1 (s[j]=」(」or」[」 ] , f[I,j-1]+1(s[j]=」)」or」]」 )

74 棋盤切割

-----線型動態規劃

f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],

f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]

min{}}

75 概率動態規劃

-----聰聰和可可(NOI2005)

x:=p[p[i,j],j]

f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1

f[I,i]=0

f[x,j]=1

76 概率動態規劃

-----血緣關系

我們正在研究妖怪家族的血緣關系。每個妖怪都有相同數量的基因，但是不同的妖怪的基因可能是不同的。我們希望知道任意給定的兩個妖怪之間究竟有多少相同的基因。由於基因數量相當龐大，直接檢測是行不通的。但是，我們知道妖怪家族的家譜，所以我們可以根據家譜來估算兩個妖怪之間相同基因的數量。

妖怪之間的基因繼承關系相當簡單：如果妖怪C是妖怪A和B的孩子，則C的任意一個基因只能是繼承A或B的基因，繼承A或B的概率各佔50％。所有基因可認為是相互獨立的，每個基因的繼承關系不受別的基因影響。

現在，我們來定義兩個妖怪X和Y的基因相似程度。例如，有一個家族，這個家族中有兩個毫無關系(沒有相同基因)的妖怪A和B，及它們的孩子C和D。那麼C和D相似程度是多少呢？因為C和D的基因都來自A和B，從概率來說，各佔50％。所以，依概率計算C和D平均有50％的相同基因，C和D的基因相似程度為50％。需要注意的是，如果A和B之間存在相同基因的話，C和D的基因相似程度就不再是50％了。

你的任務是寫一個程序，對於給定的家譜以及成對出現的妖怪，計算它們之間的基因相似程度。

F[A, B]=(f[A0, B]+P[A1, B])/2

f[I,i]=1

f[I,j]=0(I,j無相同基因)

77 線性動態規劃

-----決斗

F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] or e[j,k]),i<k<j

78 線性動態規劃

-----舞蹈家

F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]])

79 線性動態規劃

-----積木游戲

F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k』],f[I,a+1,a+1,k』])

80 樹形動態規劃（雙次記錄）

-----NOI2003 逃學的小孩

樸素的話枚舉節點i和離其最遠的兩個節點 j,k O(n^2)

每個節點記錄最大的兩個值，並記錄這最大值分別是從哪個相鄰節點傳過來的。當遍歷到某個孩子節點的時候，只需檢查最大值是否是從該孩子節點傳遞來的。如果是，就取次大，否則取最大值

81 樹形動態規劃(完全二叉樹)

-----NOI2006 網路收費

F[I,j,k]表示在點i所管轄的所有用戶中，有j個用戶為A，在I的每個祖先u上，如果N[a]>N[b]則標0否則標1，用二進制狀態壓縮進k中，在這種情況下的最小花費

F[I,j,k]:=min{ f[l,u,k and (s[i]<<(i-1))]

+w1,f[r,j-u,k and(s[i]<<(i-1))]}

82 樹形動態規劃

-----IOI2005 河流

F[i]:=max

83 記憶化搜索

-----Vijos某題,忘了

F[pre,h,m]:=sigma{SDP(I,h+1,M+i)} (pre<=i<=M＋1)

84 狀態壓縮動態規劃

-----APIO 2007 動物園

f[I,k]:=f[i-1,k and not (1<<4)] + NewAddVal

85 樹形動態規劃

-----訪問術館

f[i,j-c[i]×2]:= max ( f[l[i],k], f[r[i],j-c[i]×2-k] )

86 字元串動態規劃

-----Ural 1002 Phone

if exist((s,j,i-j)) then f[i]:=min(f[i],f[j]+1);

87 多進程動態規劃

-----CEOI 2005 service

Min( f[i,j,k], f[i-1,j,k] + c[t[i-1],t[i]] )

Min( f[i,t[i-1],k], f[i-1,j,k] + c[j,t[i]] )

Min( f[i,j,t[i-1]], f[i-1,j,k] + c[k,t[i]] )

88 多進程動態規劃

-----Vijos1143 三取方格數

max(f[i,j,k,l],f[i-1,j-R[m,1],k-R[m,2],l-R[m,3]]);

if (j=k) and (k=l) then inc(f[i,j,k,l],a[j,i-j]) else

if (j=k) then inc(f[i,j,k,l],a[j,i-j]+a[l,i-l]) else

if (k=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else

if (j=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else

inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]+a[l,i-l]);

89 線型動態規劃

-----IOI 2000 郵局問題

f[i,j]:=min(f[I,j],f[k,j-1]+d[k+1,i]);

90 線型動態規劃

-----Vijos 1198 最佳課題選擇

if j-k>=0 then Min(f[i,j],f[i-1,j-k]+time(i,k));

91 背包問題

----- USACO Raucous Rockers

多個背包，不可以重復放物品，但放物品的順序有限制。

F[I,j,k]表示決策到第i個物品、第j個背包，此背包花費了k的空間。

f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t[i]]+p[i],f[i-1,j-1,maxtime-t[i]])

92 多進程動態規劃

-----巡遊加拿大（IOI95、USACO）

d[i,j]=max{d[k,j]+1(a[k,i] & j<k<i),d[j,k]+1(a[I,j] & (k<j))}。

f[i,j]表示從起點出發，一個人到達i，另一個人到達j時經過的城市數。d[i,j]=d[j,i]，所以我們限制i>j

分析狀態(i,j)，它可能是(k,j)(j<k<i)中k到達i得到（方式1），也可能是(j,k)(k<j)中k超過j到達i得到（方式2）。但它不能是(i,k)(k<j)中k到達j得到，因為這樣可能會出現重復路徑。即使不會出現重復路徑，那麼它由(j,k)通過方式2同樣可以得到，所以不會遺漏解 時間復雜度O(n3)

93 動態規劃

-----ZOJ cheese

f[i,j]:=f[i-kk*zl[u,1],j-kk*zl[u,2]]+a[i-kk*zl[u,1],j-kk*zl[u,2]]

94 動態規劃

-----NOI 2004 berry 線性

F[I,1]:=s[i]

F[I,j]:=max{min{s[i]-s[l-1]},f[l-1,j-1]} (2≤j≤k, j≤l≤i)

95 動態規劃

-----NOI 2004 berry 完全無向圖

F[I,j]:=f[i-1,j] or (j≥w[i]) and (f[i-1,j-w[i]])

96 動態規劃

-----石子合並 四邊形不等式優化

m[i,j]=max{m[i+1,j], m[i,j-1]}+t[i,j]

97 動態規劃

-----CEOI 2005 service
（k≥long[i]，i≥1）g[i, j, k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}

（k<long[i]，i≥1） g[i, j, k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}

(0≤j≤m， 0≤k<t) g[0,j,k]=0;

ans:=g[n,m,0]。

狀態優化：g[i, j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}

其中(a, b)+long[i]=(a』, b』)的計算方法為：

當b+long[i] ≤t時： a』=a; b』=b+long[i];

當b+long[i] ＞t時： a』=a+1; b』=long[i];

規劃的邊界條件：

當0≤i≤n時，g[i,0]=(0,0)

98 動態規劃

-----AHOI 2006寶庫通道

f[k]:=max{f[k-1]+x[k,j]-x[k,i-1], x[k,j]-x[k,i-1]}

for i:= 1 to n do

begin

for j:= 1 to m do

begin

read(a[i,j]);

if a[i,j]='1' then x[i,j]:=x[i,j-1]+1

else x[i,j]:=x[i,j-1]-1;

end;

readln;

end;

for i:= 1 to m do

for j:= i to m do

begin

y:=0;

for k:= 1 to n do

begin

z:=x[k,j]-x[k,i-1];

if y>0 then inc(y,z) else y:=z;

if y>ans then ans:=y;

end;

end;

99 動態規劃

-----Travel

A) 費用最少的旅行計劃。

設f[i]表示從起點到第i個旅店住宿一天的最小費用；g[i]表示從起點到第i個旅店住宿一天，在滿足最小費用的前提下所需要的最少天數。那麼：

f[i]=f[x]+v[i], g[i]=g[x]+1

x滿足：

1、 x<i，且d[i] – d[x] <= 800（一天的最大行程）。

2、 對於所有的t < i, d[i] – d[t] <= 800，都必須滿足：

A. g[x] < g[t](f[x] = f[t]時) B. f[x] < f[t] (其他情況)

f[0] = 0，g[0] = 0。 Ans:=f[n + 1]，g[n+1]。

B). 天數最少的旅行計劃。

方法其實和第一問十分類似。

設g』[i]表示從起點到第i個旅店住宿一天的最少天數；f』[i]表示從起點到第i個旅店住宿一天，在滿足最小天數前提下所需要的最少費用。那麼：

g』[i] = g』[x] + 1, f』[i] = f』[x] + v[i]

x滿足：

1、 x<i，且d[i] – d[x] <= 800（一天的最大行程）。

2、 對於所有的t < i, d[i] – d[t] <= 800，都必須滿足：

f』[x] < f』[t] g』[x] = g』[t]時

g』[x] < g』[t] 其他情況

f』[0] = 0，g』[0] = 0。 Ans:=f』[n + 1]，g』[n+1]。

100 動態規劃

-----NOI 2007 cash

y:=f[j]/(a[j]*c[j]+b[j]);

g:=c[j]*y*a[i]+y*b[i];

f[i]:=max(f[i],g)

㈡ 2、灰度圖像壓縮/解壓縮類的實現（動態規劃演算法的應用）

http://www.zonghezy.com
http://www.zonghezy.net
http://www.hehezy.cn
http://www.fqwgwz.cn
http://hehezy.cn
綜合軟體站
進去看看

㈢ 先跪,求用動態規劃壓縮8點陣圖的c++程序,也可解壓的~學數據結構實力~

數據壓縮演算法和動態規劃有什麼直接關系...

㈣ 西南交大acm動態規劃問題有哪些

ACM常用演算法及練習
第一階段：練經典常用演算法，下面的每個演算法給我打上十到二十遍，同時自己精簡代碼，
因為太常用，所以要練到寫時不用想，10-15分鍾內打完，甚至關掉顯示器都可以把程序打
出來.
1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成樹(先寫個prim,kruscal要用並查集，不好寫)
3.大數（高精度）加減乘除
4.二分查找. (代碼可在五行以內)
5.叉乘、判線段相交、然後寫個凸包.
6.BFS、DFS,同時熟練hash表(要熟，要靈活,代碼要簡)
7.數學上的有：輾轉相除（兩行內），線段交點、多角形面積公式.
8. 調用系統的qsort, 技巧很多，慢慢掌握.
9. 任意進制間的轉換

第二階段：練習復雜一點，但也較常用的演算法。
如：
1. 二分圖匹配（匈牙利），最小路徑覆蓋
2. 網路流，最小費用流。
3. 線段樹.
4. 並查集。
5. 熟悉動態規劃的各個典型：LCS、最長遞增子串、三角剖分、記憶化dp
6.博弈類演算法。博弈樹，二進製法等。
7.最大團，最大獨立集。
8.判斷點在多邊形內。
9. 差分約束系統.
10. 雙向廣度搜索、A*演算法，最小耗散優先.

相關的知識

圖論

路徑問題
0/1邊權最短路徑
BFS
非負邊權最短路徑（Dijkstra）
可以用Dijkstra解決問題的特徵
負邊權最短路徑
Bellman-Ford
Bellman-Ford的Yen-氏優化
差分約束系統
Floyd
廣義路徑問題
傳遞閉包
極小極大距離 / 極大極小距離
Euler Path / Tour
圈套圈演算法
混合圖的 Euler Path / Tour
Hamilton Path / Tour
特殊圖的Hamilton Path / Tour 構造

生成樹問題
最小生成樹
第k小生成樹
最優比率生成樹
0/1分數規劃
度限制生成樹

連通性問題
強大的DFS演算法
無向圖連通性
割點
割邊
二連通分支
有向圖連通性
強連通分支
2-SAT
最小點基

有向無環圖
拓撲排序
有向無環圖與動態規劃的關系

二分圖匹配問題
一般圖問題與二分圖問題的轉換思路
最大匹配
有向圖的最小路徑覆蓋
0 / 1矩陣的最小覆蓋
完備匹配
最優匹配
穩定婚姻

網路流問題
網路流模型的簡單特徵和與線性規劃的關系
最大流最小割定理
最大流問題
有上下界的最大流問題
循環流
最小費用最大流 / 最大費用最大流

弦圖的性質和判定

組合數學

解決組合數學問題時常用的思想
逼近
遞推 / 動態規劃
概率問題
Polya定理

計算幾何 / 解析幾何

計算幾何的核心：叉積 / 面積
解析幾何的主力：復數

基本形
點
直線，線段
多邊形

凸多邊形 / 凸包
凸包演算法的引進，卷包裹法

Graham掃描法
水平序的引進，共線凸包的補丁

完美凸包演算法

相關判定
兩直線相交
兩線段相交
點在任意多邊形內的判定
點在凸多邊形內的判定

經典問題
最小外接圓
近似O(n)的最小外接圓演算法
點集直徑
旋轉卡殼，對踵點
多邊形的三角剖分

數學 / 數論

最大公約數
Euclid演算法
擴展的Euclid演算法
同餘方程 / 二元一次不定方程
同餘方程組

線性方程組
高斯消元法
解mod 2域上的線性方程組
整系數方程組的精確解法

矩陣
行列式的計算
利用矩陣乘法快速計算遞推關系

分數
分數樹
連分數逼近

數論計算
求N的約數個數
求phi(N)
求約數和
快速數論變換
……

素數問題
概率判素演算法
概率因子分解

數據結構

組織結構
二叉堆
左偏樹
二項樹
勝者樹
跳躍表
樣式圖標
斜堆
reap

統計結構
樹狀數組
虛二叉樹
線段樹
矩形面積並
圓形面積並

關系結構
Hash表
並查集
路徑壓縮思想的應用

STL中的數據結構
vector
deque
set / map

動態規劃 / 記憶化搜索

動態規劃和記憶化搜索在思考方式上的區別

最長子序列系列問題
最長不下降子序列
最長公共子序列
最長公共不下降子序列

一類NP問題的動態規劃解法

樹型動態規劃

背包問題

動態規劃的優化
四邊形不等式
函數的凸凹性
狀態設計
規劃方向

線性規劃

常用思想

二分 最小表示法

串

KMP Trie結構
後綴樹/後綴數組 LCA/RMQ
有限狀態自動機理論

排序
選擇/冒泡 快速排序 堆排序 歸並排序
基數排序 拓撲排序 排序網路

中級:
一.基本演算法:
(1)C++的標准模版庫的應用. (poj3096,poj3007)
(2)較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
(1)差分約束系統的建立和求解. (poj1201,poj2983)
(2)最小費用最大流(poj2516,poj2516,poj2195)
(3)雙連通分量(poj2942)
(4)強連通分支及其縮點.(poj2186)
(5)圖的割邊和割點(poj3352)
(6)最小割模型、網路流規約(poj3308, )
三.數據結構.
(1)線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)靜態二叉檢索樹. (poj2482,poj2352)
(3)樹狀樹組(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)並查集的高級應用. (poj1703,2492)
(6)KMP演算法. (poj1961,poj2406)
四.搜索
(1)最優化剪枝和可行性剪枝
(2)搜索的技巧和優化 (poj3411,poj1724)
(3)記憶化搜索(poj3373,poj1691)

五.動態規劃
(1)較為復雜的動態規劃(如動態規劃解特別的施行商問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
(3)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
(1)組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.

(2)數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
(3)計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)隨機化演算法(poj3318,poj2454)
(5)雜題.
(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
(1)坐標離散化.
(2)掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的內核(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高級:
一.基本演算法要求:
(1)代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正確性和高效性. poj3434
二.圖演算法:
(1)度限制最小生成樹和第K最短路. (poj1639)
(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優比率生成樹. (poj2728)
(4)最小樹形圖(poj3164)
(5)次小生成樹.
(6)無向圖、有向圖的最小環
三.數據結構.
(1)trie圖的建立和應用. (poj2778)
(2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法
(RMQ+dfs)).(poj1330)
(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的
目的). (poj2823)
(4)左偏樹(可合並堆).
(5)後綴樹(非常有用的數據結構,也是賽區考題的熱點).
(poj3415,poj3294)
四.搜索
(1)較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
(1)需要用數據結構優化的動態規劃.
(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.
(3)較難的狀態DP(poj3133)
六.數學
(1)組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
(2)博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點集最小圓覆蓋.
(4)對踵點(poj2079)
八.綜合題.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

初期:
一.基本演算法:
(1)枚舉. (poj1753,poj2965) (2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法. (4)遞推.
(5)構造法.(poj3295) (6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
(1)圖的深度優先遍歷和廣度優先遍歷.
(2)最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓撲排序 (poj1094)
(5)二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
(6)最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
(3)簡單並查集的應用.
(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(poj3253)
(6)堆
(7)trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
(1)深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
(1)背包問題. (poj1837,poj1276)
(2)型如下表的簡單DP(可參考lrj的書 page149):
1.E[j]=opt (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt (最長公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt.(最優二分檢索樹問題)
六.數學
(1)組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
(2)數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
(3)計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
(1)幾何公式.
(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
(3)多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)

㈤ 狀態壓縮動態規劃 怎麼寫

度前10頁巡視，同學們要自己寫，或者信曾哥。。。。。

㈥ 動態規劃演算法如何實現 .bmp灰度圖像壓縮的壓縮與解壓縮啊

誒，轉回來了。但是還差一點。。到底是哪呢。。

㈦ 動態規劃演算法（pascal）

在計算夠不夠開銷時
20%這個數據是廢的
你可以先減去預算再考慮存多少錢
比如手頭錢的數目為a
預算為b
存在媽媽處的錢為c
可以先從a中減去b
然後c就等於c+a
div
100
*100
var
略
begin
a:=0;
c:=0;
bo:=true;
for
i:=1
to
12
do
begin
read(b[i]);
inc(a,300);
if
a<b[i]
then
begin
writeln(i);
bo:=false;
break;
end
else
begin
c:=c+a
div
100*100;
dec(a,b[i]);
a:=a
mod
100;
end;
end;
if
bo
then
writeln(a+c+c
div
5);
end.

㈧ oier的知識能力體系

數學離散數學集合論 關系 代數系統 數理邏輯 圖論
組合數學排列組合 母函數 群論 遞推與遞歸 莫比烏斯反演
數學線性規劃 動態 整數
高等數學向量 行列式與矩陣 微積分初步
概率統計
初等數論素數 整數理論 同餘與模線性方程
計算幾何
數據結構存儲結構線性表
（一級結構）靜態：數組 棧 隊列 廣義表 字元串
動態：指針鏈表 動態數組
樹
（二級結構）表示法（靜態、動態） 二叉樹 森林
圖
（三級結構）表示法（矩陣、鄰接表、三元組）
特殊結構散列表（HASH表） 並查集 線段樹 後綴樹 哈夫曼樹與哈夫曼編碼 地址表Bit圖 滾動數組 棋盤圖 邊頂置換圖 二分點圖（網路流）
常用方法遍歷樹 圖 前/中/後序優先
轉化拓撲排序（三級結構轉一級結構） 最小生成樹 最小樹形圖（三級結構轉二級結構） 逆遍歷
壓縮路徑樹的線索化
壓縮存儲
查找線性直接 折半Fab
樹形二叉查找樹 平衡二叉樹B+樹B-樹 線索二叉樹索引表
排序插入排序直接排序、折半排序、2-路排序
交換排序冒泡排序 快速排序 歸並排序
堆排序
基數排序鏈式基數排序 桶排序
代碼素養代碼的編寫速度和准確性 誤碼率
演算法實現
演算法優化
調試 查錯 測試
習慣變數名 注釋 縮進 模塊化
基本演算法數學高精度計算（模擬計算）
表達式處理括弧 前/中/後綴表達式 表達式樹
排列組合求值 嵌套控制
高斯消元法
快速傅里葉變換（FFT）
篩選素數素數表
分數處理
基本操作實現大量數據賦值與移動Fillchar fillword move等函數
處理實數比較大小 高精度
字元串處理基本函數KMP演算法
圖論
（顯示圖搜索）路徑問題
（邊集）連通性測試傳遞閉包演算法 極大強連通子圖 最小點基
最短路問題標號法 第k小路 減半最短路Dijkstra演算法floyd演算法bellman-ford演算法Warshall演算法
特殊路徑歐拉路及迴路 哈密爾頓路及迴路
圖的中心和重心
生成樹Kruskal演算法Prim演算法
集
（頂點集）覆蓋集
獨立集
支配集
割頂和塊
網路流容量有上下界的網路最大/ 小流
容量有上下界的網路最小費用最大/ 小流
頂容量網路最大流
供求約束可行流
二分圖匹配匈牙利演算法
關鍵路徑
搜索
（隱式圖搜索）深度優先搜索
（回溯法）剪枝優化
預處理
記憶化搜索
可變下界的深度優先搜索
隨機化搜索
廣度優先搜索雙向廣搜*多向廣搜
啟發式搜索（A演算法）
分枝定界
多階段決策貪心演算法
背包動態規劃
棋盤動態規劃
劃分動態規劃
區間動態規劃
樹形動態規劃
狀態壓縮型動態規劃
其他構造法窮舉
模擬