我們經(jīng)常會(huì)遇到這樣一類問(wèn)題，比如有一些物品，每個(gè)物品都有兩個(gè)屬性，其中每個(gè)屬性都是可比的，比如我們有一摞圓形燒餅，每個(gè)燒餅有直徑和重量?jī)蓚€(gè)屬性，且這兩個(gè)屬性不相關(guān)。那么我們?nèi)绾螌⑦@些燒餅分成盡量少的堆，使得每堆燒餅都可以滿足質(zhì)量和直徑均單調(diào)增（或者單調(diào)減）？
首先直觀的想法是第一步肯定得按照質(zhì)量（或者直徑，均可）從小到大排序。排序完成之后質(zhì)量已經(jīng)滿足要求了，但是直徑并不一定也按照遞增排好序了。該如何將該按質(zhì)量排好序的序列分成最少數(shù)量的若干個(gè)子序列，使得子序列能夠同時(shí)按照直徑遞增排列？
這時(shí)候Dilworth定理就派上用場(chǎng)了。
Dilworth定理大概意思是說(shuō)：對(duì)于一個(gè)偏續(xù)集(X,<=)，其最少鏈劃分?jǐn)?shù)等于其最長(zhǎng)反鏈的長(zhǎng)度。其中鏈的意思是滿足a1<=a2<=a3<=...<=ai的i個(gè)偏序集中的元素。這里的<=并不一定是小于等于的意思，只是表達(dá)的是一種偏序關(guān)系。
Dilworth定理的證明就不說(shuō)了，網(wǎng)上有現(xiàn)成的證明。
下面說(shuō)說(shuō)利用Dilworth定理來(lái)解決上面提到的問(wèn)題。
心急的C小加問(wèn)題摘自
http://acm.nyist.net/JudgeOnline/problem.php?pid=236 該問(wèn)題和上面提到的燒餅問(wèn)題類似，只不過(guò)改成了木棒，它要求將一堆木棒分成最少的堆數(shù)，使得每小堆木棒都能夠按照長(zhǎng)度和質(zhì)量均遞增的順序排列。典型的Dilworth定理問(wèn)題。
其實(shí)講木棒按照長(zhǎng)度遞增排列之后，對(duì)質(zhì)量的處理就成了尋找最長(zhǎng)遞減子序列的問(wèn)題了。該問(wèn)題有O(nlogn)的解法，不過(guò)先看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的遞減子序列的長(zhǎng)度
14 int cur_maxlen_include_i[MAX];
15 //cur_max_minelem[i]代表長(zhǎng)度為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 //求最長(zhǎng)遞減子序列
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 }
該程序提交后運(yùn)行時(shí)間為228ms
接下來(lái)是采用二分加速來(lái)查找最長(zhǎng)遞減子序列，程序如下：
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的遞減子序列的長(zhǎng)度
14 int cur_maxlen_include_i[MAX];
15 //cur_max_minelem[i]代表長(zhǎng)度為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 //求最長(zhǎng)遞減子序列
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 }
二分加速提交后運(yùn)行時(shí)間反而為264ms，運(yùn)行時(shí)間慢了，說(shuō)明題目的測(cè)試數(shù)據(jù)可能并不十分均勻。
posted on 2012-09-18 16:47
myjfm 閱讀(540)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)