队形算法

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背包问题
开心的金明
金明的预算方案
加分二叉树
字串编辑距离
花瓶插花
凸多边形三角划分
快餐店