【历年代码】

【17上】

找假币 假币轻

1）for(i=first;i<first+(last-first)/2+1;i++)    //左半区

2）if(firstsum<lastsum);                                //左边轻

3）return first+(last-first)/2;                          //左边=右边，中间假币

4）分治

5）O(log2n)

6）2

7）4

【17下】

汉密尔顿回路 无向连通图

1）visited[0]=1

2）visited[x[k]]==0

3）c[x[k]][0]==1

4）visited[x[k]]=1

5）k=k-1

6）回溯

7）深度优先

【18上】

钢条最大价值

1）i<=n 

2）i<=j

3）temp>=p[i]+r[j-i]?temp:p[i]+r[j-i]

4）r[j]=temp

5）动态规划

6）O(2的n方)

7）O(n2)

【18下】

字符序列二级结构最优配对

1）max=C[i][j-1]

2）t=i

3）isMatch(B[t],B[j])

4）C[1][n]

5）动态规划

6）O(n3)

7）2

【19上】

N皇后

1）queen[i]==queen[j]

2）1

3）Place(j)            //j是行 改行可摆

4）Nqueen(j+1)

5）回溯法

6）2

7）（3,1,4,2）（2,4,1,3）

【19下】

01背包

1）c[i][j]

2）w[i]<=j

3）Caclulate_Max_Value(v,w,i,j-w[i])+v[i]

4）c[i][j]=temp

5）动态规划

6）自顶向下

7）40

【20下】

希尔排序

1）k=k/2

2）k>1

3）data[k-dk]>data[k]

4）data[j+dk]=t

5）x小于

6）否

7）（4,9，-1，8,20,7，15）

【21上】

凸多边形最优剖分方案

1）i <= N

2）j = i + r - 1

3）temp < m[i][j]

4）S[i][j] + 1, j

5）动态规划

6）O（n3）

7）O（n2）

【22上】

矩阵连乘

1）j=i+p;

2）k<j;

3）cost[i][k]+cost[k+1][j]+seq[i]*seq[k+1]*seq[j+1]

4）trace[i][j]=tempTrace;

5）动态规划

6）O(n3)

7）5375

15*5    5*10    10*20    20*25

1            2            3            4

2*3 先    5*10*20=1000,5*20

23*4       5*20*25=2500,5*25

1*234        15*5*25=1875，

1*(23*4)    5375

,,

3*4 先    10*20*25=5000,10*25

2*34    5*10*25=750