我們經常會遇到這樣一類問題，比如有一些物品，每個物品都有兩個屬性，其中每個屬性都是可比的，比如我們有一摞圓形燒餅，每個燒餅有直徑和重量兩個屬性，且這兩個屬性不相關。那么我們如何將這些燒餅分成盡量少的堆，使得每堆燒餅都可以滿足質量和直徑均單調增（或者單調減）？
首先直觀的想法是第一步肯定得按照質量（或者直徑，均可）從小到大排序。排序完成之后質量已經滿足要求了，但是直徑并不一定也按照遞增排好序了。該如何將該按質量排好序的序列分成最少數量的若干個子序列，使得子序列能夠同時按照直徑遞增排列？
這時候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 閱讀(533)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎