NOIp中很少见的数据结构的题目，可以用堆实现，也可以用两条队列. 用堆实现，调了很久 = =
需要注意down函数的边界问题.
1
#include<stdio.h>
2#include<string.h>
3#include<iostream>
4using namespace std;
5int n, h[10010];
6
struct heap
{
7
void swap(int*i, int*j){
8
int k = *i; *i = *j; *j = k;
9
}
10 void up(int k){
11 while (k > 1)
12 if (h[k/2] > h[k]) {
13 swap(&h[k/2], &h[k]);
14 k /= 2;
15 }else break;
16 }
17 void down(int k){
18 while (2*k <= n){
19 int l = 2*k, r = l<n ? l+1 : l;
20 if (h[r] < h[l]) l++;
21 if (h[k] > h[l]){
22 swap(&h[k], &h[l]);
23 k = l;
24 }else break;
25 }
26 }
27 void insert(int x){
28 h[++n] = x;
29 up(n);
30 }
31 void del(int k){
32 swap(&h[k], &h[n--]);
33
34 down(k);
35 }
36 int pop(){
37 del(1);
38 return h[n+1];
39 }
40
};
41heap hp;
42int main(){
43 int i, sum = 0;
44 scanf("%d", &n);
45 for (i = 1; i <= n; i++)
46 scanf("%d", &h[i]);
47 for (i = n/2; i > 0; i--) hp.down(i);
48 while (n > 1){
49 int x = hp.pop(), y = hp.pop();
50 sum += x+y;
51 hp.insert(x+y);
52 }
53 printf("%d\n", sum);
54}
55
78 = 12+15+5+32+14，上80还是很困难.
1.二分查找
设内
部结点的总数为n=2^h-1，则判定树是深度为h=log(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1，查找它们所需的比较次数是k。因此在等概率假设下，二分查找成功时的平均查找长度为：ASLbn ≈ log(n+1)-1
二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。
2.问题求解第二题
21本书中选4本，任意两本编号不相邻.
去掉3个间隔，C(18,4)=3060.
排列组合题总是简单的出乎意料. = =
3.快速排序算法不熟
今天突然发现很多O(nlogn)级别的算法都和树有很深的关系，遍历的过程通常都是生成某种树，然后查找长度和比较次数通常和树的深度相关.
1.直接插入排序 O(n^2) 稳定
2.希尔排序 O(n^1.3) 不稳定
3.直接选择排序 O(n^2) 不稳定
4.堆排序 O(nlogn) 不稳定
5.冒泡排序 O(n^2) 稳定
6.快速排序 O(nlogn) 不稳定 =>可以看做构造二叉排序树
7.归并排序 O(nlogn) 稳定
整理自《奥赛经典·信息学》 第5章，原理略.
[原文]http://blog.csdn.net/guocai_yao/archive/2009/04/11/4065718.aspx
1.树的遍历法
通过中缀表达式，构造表达式树，然后利用前序或者后序遍历.
2.括号转移法
这里我给出一个中缀表达式
a+b*c-(d+e)
第一步：按照运算符的优先级对所有的运算单位加括号
式子变成拉：((a+(b*c))-(d+e))
第二步：转换前缀与后缀表达式
前缀：把运算符号移动到对应的括号前面
则变成拉：-( +(a *(bc)) +(de))
把括号去掉：-+a*bc+de 前缀式子出现
后缀：把运算符号移动到对应的括号后面
则变成拉：((a(bc)* )- (de)+ )-
把括号去掉：abc*-de+- 后缀式子出现
发现没有，前缀式，后缀式是不需要用括号来进行优先级的确定的。
树
形DP，需要记录方案，并注意空树的情况.[状态]f[i][j]从结点i到j的最大加分值[方程]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)实现方程的时候循环顺序非常关键:结点数由小到大循环.否则会出现需要的值未计算的情况.记录方案可以用一个数组d[i][j]记录k，然后递归寻找方案并记录.
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[35][35] = {0}, d[35][35] = {0}, ans[35] = {0}, t = 0;
5 void print(int start, int end){
6 if (start > end) return;
7 if (start == end) {ans[++t] = start; return;}
8 ans[++t] = d[start][end];
9 print(start, d[start][end]-1);
10 print(d[start][end]+1, end);
11 }
12 int main(){
13 int n, a[35] = {0}, i, j, k, l;
14 scanf("%d", &n);
15 for (i = 1; i <= n; i++){
16 scanf("%d", &a[i]);
17 f[i][i-1] = 1;
18 f[i][i] = a[i];
19 }
20 for (l = 2; l <= n; l++)
21 for (i = 1; i <= n; i++)
22 for (k = i; k <= i+l-1; k++){
23 j = i+l-1;
24 if (f[i][j] < f[i][k-1]*f[k+1][j] + a[k]){
25 f[i][j] = f[i][k-1]*f[k+1][j] + a[k];
26 d[i][j] = k;
27 }
28 }
29 printf("%d\n", f[1][n]);
30 print(1, n);
31 for (i = 1; i < t; i++) printf("%d ", ans[i]);
32 printf("%d\n", ans[t]);
33 }
34
题目中附件不超过2个，因而主附件存在4种不同的存取情况，可以转化为分组背包问题.[状态]f[k][v]表示添加前k组物品，剩余空间为v时的最大值[方程]f[k][v] = max{f[k-1][v], f[k-1][v-c[i]]+w[i]}注意循环顺序.(参见《背包九讲》)需要注意的问题(2次WA):1.仔细读题，确定编号对应的物品.2.注意到方程中的参数非负(背包类问题需注意).
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 using namespace std;
5 int c[65][4], w[65][4], f[32000], set[70] = {0};
6 int max(int a, int b){return a > b ? a : b;}
7 int main(){
8 int n, m, v, p, q, i, j, t = 0;
9 FILE *fout = fopen("budget.out", "w");
10 memset(c, -1, sizeof(c));
11 memset(w, -1, sizeof(w));
12 memset(f, 0, sizeof(f));
13 scanf("%d%d", &n, &m);
14 for (i = 0; i < m; i++){
15 scanf("%d%d%d", &v, &p, &q);
16 j = 0;
17 if (!q) {
18 c[++t][0] = v;
19 w[t][0] = v*p;
20 set[i+1] = t;
21 }
22 else{
23 q = set[q];
24 if (w[q][1] == -1){
25 //printf("dgfdgds\n");
26 c[q][1] = c[q][0] + v;
27 w[q][1] = w[q][0] + v*p;
28 }
29 else if (w[q][2] == -1){
30 c[q][2] = c[q][0] + v;
31 w[q][2] = w[q][0] + v*p;
32 c[q][3] = c[q][1] + v;
33 w[q][3] = w[q][1] + v*p;
34 }
35 }
36 }
37 for (i = 1; i <= t; i++)
38 for (v = n; v >= 0; v--)
39 for (j = 0; j < 4; j++)
40 if (c[i][j] != -1 && v-c[i][j] >= 0){
41 f[v] = max(f[v], f[v-c[i][j]]+w[i][j]);
42 }
43 printf("%d\n", f[n]);
44 }
45