我们经常会遇到这样一类问题，比如有一些物品，每个物品都有两个属性，其中每个属性都是可比的，比如我们有一摞圆形烧饼，每个烧饼有直径和重量两个属性，且这两个属性不相关。那么我们如何将这些烧饼分成尽量少的堆，使得每堆烧饼都可以满足质量和直径均单调增（或者单调减）？
首先直观的想法是第一步肯定得按照质量（或者直径，均可）从小到大排序。排序完成之后质量已经满足要求了，但是直径并不一定也按照递增排好序了。该如何将该按质量排好序的序列分成最少数量的若干个子序列，使得子序列能够同时按照直径递增排列？
这时候Dilworth定理就派上用场了。
Dilworth定理大概意思是说：对于一个偏续集(X,<=)，其最少链划分数等于其最长反链的长度。其中链的意思是满足a1<=a2<=a3<=...<=ai的i个偏序集中的元素。这里的<=并不一定是小于等于的意思，只是表达的是一种偏序关系。
Dilworth定理的证明就不说了，网上有现成的证明。
下面说说利用Dilworth定理来解决上面提到的问题。
心急的C小加问题摘自
http://acm.nyist.net/JudgeOnline/problem.php?pid=236 该问题和上面提到的烧饼问题类似，只不过改成了木棒，它要求将一堆木棒分成最少的堆数，使得每小堆木棒都能够按照长度和质量均递增的顺序排列。典型的Dilworth定理问题。
其实讲木棒按照长度递增排列之后，对质量的处理就成了寻找最长递减子序列的问题了。该问题有O(nlogn)的解法，不过先看O(n
2)的解法：
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4
5 #define MAX 5005
6
7 typedef struct {
8 int weight;
9 int length;
10 }STICK;
11
12 STICK sticks[MAX];
13 //cur_maxlen_include_i[i]代表包含元素sticks[i].length的递减子序列的长度
14 int cur_maxlen_include_i[MAX];
15 //cur_max_minelem[i]代表长度为i的递减子序列的最小元素的最大值
16 int cur_max_minelem[MAX];
17
18 int cmp(const void *a, const void *b) {
19 STICK *x = (STICK *)a;
20 STICK *y = (STICK *)b;
21 if (x->length != y->length) {
22 return x->length - y->length;
23 } else {
24 return x->weight - y->weight;
25 }
26 }
27
28 int main() {
29 int T;
30 scanf("%d", &T);
31 while (T--) {
32 int N;
33 int i, j;
34 scanf("%d", &N);
35 for (i = 0; i < N; ++i) {
36 scanf("%d%d", &(sticks[i].length), &(sticks[i].weight));
37 }
38 qsort(sticks, N, sizeof(STICK), cmp);
39
40 //求最长递减子序列
41 memset(cur_maxlen_include_i, 0, sizeof(int) * MAX);
42 memset(cur_max_minelem, 0, sizeof(int) * MAX);
43
44 cur_maxlen_include_i[0] = 1;
45 cur_max_minelem[1] = sticks[0].weight;
46
47 int cur_maxlen = 1;
48 for (i = 1; i < N; ++i) {
49 cur_maxlen_include_i[i] = 1;
50 for (j = cur_maxlen; j > 0; --j) {
51 if (cur_max_minelem[j] > sticks[i].weight) {
52 cur_maxlen_include_i[i] = j + 1;
53 break;
54 }
55 }
56 if (cur_maxlen_include_i[i] > cur_maxlen) {
57 cur_maxlen = cur_maxlen_include_i[i];
58 cur_max_minelem[cur_maxlen] = sticks[i].weight;
59 } else if (cur_max_minelem[cur_maxlen_include_i[i]] < sticks[i].weight) {
60 cur_max_minelem[cur_maxlen_include_i[i]] = sticks[i].weight;
61 }
62 }
63 printf("%d\n", cur_maxlen);
64 }
65 return 0;
66 }
该程序提交后运行时间为228ms
接下来是采用二分加速来查找最长递减子序列，程序如下：
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4
5 #define MAX 5005
6
7 typedef struct {
8 int weight;
9 int length;
10 }STICK;
11
12 STICK sticks[MAX];
13 //cur_maxlen_include_i[i]代表包含元素sticks[i].length的递减子序列的长度
14 int cur_maxlen_include_i[MAX];
15 //cur_max_minelem[i]代表长度为i的递减子序列的最小元素的最大值
16 int cur_max_minelem[MAX];
17
18 int cmp(const void *a, const void *b) {
19 STICK *x = (STICK *)a;
20 STICK *y = (STICK *)b;
21 if (x->length != y->length) {
22 return x->length - y->length;
23 } else {
24 return x->weight - y->weight;
25 }
26 }
27
28 int main() {
29 int T;
30 scanf("%d", &T);
31 while (T--) {
32 int N;
33 int i, j;
34 scanf("%d", &N);
35 for (i = 0; i < N; ++i) {
36 scanf("%d%d", &(sticks[i].length), &(sticks[i].weight));
37 }
38 qsort(sticks, N, sizeof(STICK), cmp);
39
40 //求最长递减子序列
41 memset(cur_maxlen_include_i, 0, sizeof(int) * MAX);
42 memset(cur_max_minelem, 0, sizeof(int) * MAX);
43
44 cur_maxlen_include_i[0] = 1;
45 cur_max_minelem[1] = sticks[0].weight;
46
47 int cur_maxlen = 1;
48 for (i = 1; i < N; ++i) {
49 cur_maxlen_include_i[i] = 1;
50 int low = 1;
51 int high = cur_maxlen;
52 while (low < high - 1) {
53 int mid = (low + high) >> 1;
54 if (cur_max_minelem[mid] > sticks[i].weight) {
55 low = mid;
56 } else {
57 high = mid;
58 }
59 }
60 if (cur_max_minelem[low] > sticks[i].weight) {
61 cur_maxlen_include_i[i] = low + 1;
62 }
63 if (cur_max_minelem[high] > sticks[i].weight) {
64 cur_maxlen_include_i[i] = high + 1;
65 }
66 if (cur_maxlen_include_i[i] > cur_maxlen) {
67 cur_maxlen = cur_maxlen_include_i[i];
68 cur_max_minelem[cur_maxlen] = sticks[i].weight;
69 } else if (cur_max_minelem[cur_maxlen_include_i[i]] < sticks[i].weight) {
70 cur_max_minelem[cur_maxlen_include_i[i]] = sticks[i].weight;
71 }
72 }
73 printf("%d\n", cur_maxlen);
74 }
75 return 0;
76 }
二分加速提交后运行时间反而为264ms，运行时间慢了，说明题目的测试数据可能并不十分均匀。
posted on 2012-09-18 16:47
myjfm 阅读(492)
评论(0) 编辑 收藏 引用 所属分类:
算法基础