隊形演算法

A. 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)

B. 有n個學生站成一排kava

先把演算法過程想好，在按JAVA的方式套用數學公式

C. NOIP2004合唱隊形Pascal查錯

readln(n); /*讀學生數*/
for i ← 1 to n do read(a[i]); /*讀每個學生的身高*/
fillchar(b,sizeof(b),0);fillchar(c,sizeof(c),0); /*身高滿足遞增順序的兩個隊列初始化*/
for i ← 1 to n do /*按照由左而右的順序計算b序列*/
{ b[i] ← 1;
for j ← 1 to i-1 do
if (a[i]>a[j])and(b[j]+1>b[i]) then b[i]← b[j]+1;
};/*for*/
for i ← n downto 1 do /*按照由右而左的順序計算c序列*/
{ c[i] ← 1;
for j ← i+1 to n do
if (a[j]<a[i])and(c[j]+1>c[i])then c[i] ← c[j]+1;
};/*for*/
max ← 0; /*計算合唱隊的人數max（其中1人被重復計算）*/
for i ← 1 to n do if b[i]+c[i]>max then max ← b[i]+c[i];
writeln(n-max+1); /*輸出出列人數*/

這個演算法的時間復雜度為O(n2)

你那個有些蹩腳

D. 一隊士兵，排成一個方陣，最外層一周是96人，這個方陣都少人

錯誤演算法：96/4=24，得出方陣最外層四隊，每一隊24人，24*24=576人。
因為方陣應當盡量看起來矩形，所以最外層的四隊都是首尾相接的隊形，而錯誤演算法中，這四隊並不是首尾相接，可以簡單的用最外層16人來畫圖演示，隊列實際有25人。
應當：96/2=48，得出，方陣最外層相鄰的兩隊人數減二（方陣相鄰兩隊人數應為50人），然後取相鄰（或者兩個數之差最小的兩個正整數）兩個正整數相加等於50，得出25+25=50，所以，方陣為25*25的隊形（這是和正方形最相似的陣型，如果不要求，那麼還要算其他情況，但是兩邊之和一定為50），得出方陣共有625人。

E. 請詳細講一下PASCAL合唱隊形這個DP程序，萬分感謝。

要做這道題，必須得會求最長下降子序列。

先說怎麼求以t[i]開頭到t[n]的最長下降子序列的長度：
設一個數組s，s[j]為從t[i]開始到t[j]為止最長下降子序列的長度。
初始時，s[i]=1。
計算s[j]時，從i到j-1開始枚舉，如果存在k1,k2,k3,……使得t[k1]>t[j],t[k2]>t[j],t[k3]>t[j],……，則s[j]=max(s[j-1],s[k1]+1,s[k2]+1,s[k3]+1,……)。
最終s[n]即為以t[i]開頭到t[n]的最長下降子序列的長度。

比如說數據是t=(186,186,150,200,160,130,197,220)，求以t[4]開頭的最長下降子序列的長度：
s[4]=1
200>160,s[5]=max(s[4],s[4]+1)=2
200>130,160>130,s[6]=max(s[5],s[4]+1,s[5]+1)=3
200>197,s[7]=max(s[6],s[4]+1)=3
s[8]=max(s[7])=3
以t[4]開頭的最長下降子序列的長度為3。

按照類似的方法，可以求出以t[1]開頭到t[i]的最長上升子序列的長度。
設兩個數組a,b，a[i]為以t[i]開頭到t[n]的最長下降子序列的長度，b[i]為以t[1]開頭到t[i]的最長上升子序列的長度。
用上面的方法求出每個a[i],b[i]。
a[i]+b[i]-1即為以第i個同學為中心可排出的最長合唱隊形的長度。
max(a[1]+b[1]-1,a[2]+b[2]-1,a[3]+b[3]-1,……)即為n位同學可排出的最長合唱隊形的長度。
用n減去這個值，就得到最終答案。

對於樣例數據，有：
1 2 3 4 5 6 7 8
a 3 3 2 3 2 1 1 1
b 1 1 1 2 2 1 3 4
max(a[i]+b[i]-1)=4
8-4=4，4即為答案。

以上是我的演算法，和你給出的程序不完全相同但是類似。

F. C語言高手請教:合唱隊形演算法

補充之後就懂了~~呵呵。這個程序TC下測試成功，好累，懶得寫注釋了，有時間了給你解釋。先貼出來，你到TC裡面可以直接用，沒有人機交互，例如提示輸入n之類的，你就按順序先輸入n在輸入身高就好了，不過身高輸入的時候一定要3位一空格，也就是就算只有50厘米也要輸入050再空格。後來自己又考慮了一下，演算法還是有缺陷，晚上我再想。困了。。。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int n,test[100],len,k,flag;
char *read=malloc(512*sizeof(char));
do{
k=0;
for(len=0;len<100;len++)
test[len]=0;
flag=1;
scanf("%d\n",&n);
if(n<2||n>100)
exit(0);
if(n!=0)
fgets(read,512,stdin);
len=strlen(read)-1;
read[len]='\0';
for(len=0;len<n;len++){
test[len]=atoi(read);
read+=4;
}
for(len=0;len<n;len++){
if(test[len]<test[len+1]){
flag=0;
continue;
}
else{
if(flag)
k+=1;
else
break;
}
}
for(;len<n;len++){
if(test[len]>test[len+1])
continue;
else
k+=1;
}
printf("%d\n",k);
}while(n!=0);
return 0;
}

G. 請設計一個演算法C語言C程序C編程（很難）

沒看清題目，原來你還要求——每一次的交換必須是上一組兩個同學之間的交換，其實用遞歸函數遞歸還是可以的呀！只需要增加一個數組n[4](如果是N個同學之間的交換就設n[N-1]).

deal(l)函數——它只負責找出l號位置該站哪位同學，這名同學只能從上次0~（l-1）位置上已經站好的同學中選擇出，並與l位置的同學作交換，（deal(l)函數會把「具體」找l號以下位置應該站哪些同學的任務交由deal（l-1）來處理），直到deal(0)負責0位置該站誰（此時已經結束，0號位置以下已經沒同學可與0位置同學作交換了）。
這種思想仍然是遞歸，也就是回答者： sujie325 所說的思想！

問題的關鍵是：
對於deal(l)函數，我們必須要保證每一次被交換到l號位置的同學都是不同的，用什麼來保證呢？設置一個數組n[4]！
它的作用是：
記錄l號位置的同學變動情況（l號位置的同學只能與l號位置以下的同學交換），然後利用以下語句，在0~(l-1)位置中尋找出在n[4]中沒有的同學（這名同學的位置是k），然後把此同學交換到l號位置。另外也不要忘記把l號位置的同學記錄到n[]數組中！！
============================================================================
for(k=0;k<l;k++)
{ flagy=1;
for(n_i=0;n_i<=n_p;n_i++)
{
if(b[ml][k]==n[n_i])
{flagy=0;break;}
}
if(flagy)
{break;}
}
n[++n_p]=b[ml][l];
b[m][l]=b[ml][k],b[m][k]=b[ml][l];/*第k號位置處的同學與第l號位置的同學交換位置*/
==================================================================================
整個程序在如下：
#include<stdio.h>
#define N 5
int b[120][N]={1,2,3,4,5};
int m=0;
int deal(int l)
{int i,j;
int ml;
int n[4]={0};
int n_p=-1,n_i,n_j;
int k=0;
int flagy;
if(l==0)
return ++m;

deal(l-1);
for(i=0;i<l;i++)
{ ml=m-1;
for(j=0;j<5;j++)
{
b[m][j]=b[ml][j];
}
for(k=0;k<l;k++)
{ flagy=1;
for(n_i=0;n_i<=n_p;n_i++)
{
if(b[ml][k]==n[n_i])
{flagy=0;break;}
}
if(flagy)
{break;}
}
n[++n_p]=b[ml][l];
b[m][l]=b[ml][k],b[m][k]=b[ml][l];/*第k號位置處的同學與第l號位置的同學交

換位置*/
deal(l-1);
}

}

void main()
{
int l=N-1;int i,j;unsigned char pause=0x80;
deal(l);
for(i=0;i<120;i++)
{if((pause=pause>>1)==0)
{getchar();pause=0x80;}
for(j=4;j>=0;j--)
printf("%d ",b[i][j]);
printf("\n");
}
printf("It has %d categorys in total!\n",m);

}

=====================================================================================
上次的程序（只找出120種組合情況）

#include<stdio.h>
int b[120][5]={1,2,3,4,5};
int m=0;
int deal(int l)
{int i,j;
int ml=m;
if(l==0)
return ++m;

deal(l-1);
for(i=0;i<l;i++)
{
for(j=0;j<5;j++)
{
b[m][j]=b[ml][j];
}
b[m][l]=b[ml][i],b[m][i]=b[ml][l];/*第i號同學與l號同學交換位置*/
deal(l-1);
}

}
void main()
{
int l=4;int i,j;char c=0x10;
deal(l);
for(i=0;i<120;i++)
{if((c=c>>1)==1)/*由於數據組合種類很多，這條if語句實現的是顯示暫停（getchar()）*/
{getchar();c=0x10;}
for(j=4;j>=0;j--)/*輸出組合*/
printf("%d ",b[i][j]);
printf("\n");
}
printf("the m is %d\n",m);
}

H. 無人機如何實現編隊

• 無人機編隊飛行

即多架無人機為適應任務要求而進行的某種隊形排列和任務分配的組織模式,它既包括編隊飛行的隊形產生、保持和變化,也包括飛行任務的規劃和組織。

• 無人機編隊飛行基本要求

保持各飛機直接所設定的相對姿態和相對位置，可以結合編隊模式，通過控制在隊飛機相對於某一特定點（或對象）的距離來實現.

• 無人機編隊飛行關鍵技術

  隊形保持 ；在表演時，不僅要求無人機編隊能夠保持隊形不變，還需要在飛行過程中根據任務要求能夠實現隊形變換。

  防撞避障 ；防撞是指在編隊中各個無人機之間避免相互碰撞；應當控制好編隊中無人機間飛行距離

  航跡規劃 ；無人機編隊的路徑規劃中在把編隊作為一個整體的條件下，可以看作單無人機航跡規劃進行處理。應當設置好每架飛機的飛行路徑

• 編隊表演流程

希望能幫到您，謝謝！

I. C語言中基本的幾種演算法有哪些越多越好！就像打擂台演算法'冒泡排序法等等...

排序演算法
冒泡排序
選擇排序
快速排序
高精度運算
存儲方法
加法運算
減法運算
乘法運算
擴大進制數
習題與練習
搜索演算法
枚舉演算法
深度優先搜索
廣度優先搜索
8數碼問題
n皇後問題
搜索演算法習題
枚舉法習題
聰明的打字員
量水問題
染色問題
跳馬問題
算24點
圖論演算法
最小生成樹演算法(Prim演算法)
單源最短路徑演算法(Dijkstra演算法)
任意結點最短路徑演算法(Floyd演算法)
求有向帶權圖的所有環
Bellman-Ford演算法
計算圖的連通性
計算最佳連通分支
計算拓撲序列
圖論演算法習題
網路建設問題
最短變換問題
挖地雷
烏托邦城市
烏托邦交通中心
動態規劃
最短路徑問題
動態規劃概念
騎士游歷問題
最長遞增子序列
合唱隊形
石子合並問題
能量項鏈
0/1背包問題
開心的金明
金明的預算方案
加分二叉樹
字串編輯距離
花瓶插花
凸多邊形三角劃分
快餐店