青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆-80  評論-24  文章-0  trackbacks-0
我們經(jīng)常會遇到這樣一類問題,比如有一些物品,每個物品都有兩個屬性,其中每個屬性都是可比的,比如我們有一摞圓形燒餅,每個燒餅有直徑和重量兩個屬性,且這兩個屬性不相關(guān)。那么我們?nèi)绾螌⑦@些燒餅分成盡量少的堆,使得每堆燒餅都可以滿足質(zhì)量和直徑均單調(diào)增(或者單調(diào)減)?
首先直觀的想法是第一步肯定得按照質(zhì)量(或者直徑,均可)從小到大排序。排序完成之后質(zhì)量已經(jīng)滿足要求了,但是直徑并不一定也按照遞增排好序了。該如何將該按質(zhì)量排好序的序列分成最少數(shù)量的若干個子序列,使得子序列能夠同時按照直徑遞增排列?
這時候Dilworth定理就派上用場了。
Dilworth定理大概意思是說:對于一個偏續(xù)集(X,<=),其最少鏈劃分數(shù)等于其最長反鏈的長度。其中鏈的意思是滿足a1<=a2<=a3<=...<=ai的i個偏序集中的元素。這里的<=并不一定是小于等于的意思,只是表達的是一種偏序關(guān)系。
Dilworth定理的證明就不說了,網(wǎng)上有現(xiàn)成的證明。
下面說說利用Dilworth定理來解決上面提到的問題。
心急的C小加問題摘自http://acm.nyist.net/JudgeOnline/problem.php?pid=236 
該問題和上面提到的燒餅問題類似,只不過改成了木棒,它要求將一堆木棒分成最少的堆數(shù),使得每小堆木棒都能夠按照長度和質(zhì)量均遞增的順序排列。典型的Dilworth定理問題。
其實講木棒按照長度遞增排列之后,對質(zhì)量的處理就成了尋找最長遞減子序列的問題了。該問題有O(nlogn)的解法,不過先看O(n2)的解法:

 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,運行時間慢了,說明題目的測試數(shù)據(jù)可能并不十分均勻。
posted on 2012-09-18 16:47 myjfm 閱讀(540) 評論(0)  編輯 收藏 引用 所屬分類: 算法基礎(chǔ)
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美激情五月| 亚洲一区二区三区四区在线观看| 久久精品国产综合| 国产美女一区二区| 久久久91精品| 开心色5月久久精品| 亚洲精品国产系列| 在线天堂一区av电影| 欧美亚男人的天堂| 香蕉国产精品偷在线观看不卡| 欧美亚洲系列| 影音先锋久久精品| 亚洲国产婷婷香蕉久久久久久99| 亚洲一区二区伦理| 悠悠资源网久久精品| 亚洲国产一二三| 国产精品视频不卡| 欧美高潮视频| 欧美日韩一区二区高清| 久久久久99精品国产片| 欧美丰满高潮xxxx喷水动漫| 亚洲欧美日韩久久精品 | 亚洲午夜精品久久久久久浪潮| 亚洲视频axxx| 影音先锋日韩资源| 99国产精品视频免费观看一公开| 国产一区二区三区四区老人| 欧美激情一区在线| 国产精品久久久久久久久久久久久久 | 欧美一区二区三区成人| 日韩视频在线观看免费| 欧美一区二区精品| 亚洲天堂视频在线观看| 美女图片一区二区| 久久av在线| 国产精品成人观看视频国产奇米| 欧美成人高清视频| 国产三级精品在线不卡| 99re国产精品| 91久久黄色| 久久久爽爽爽美女图片| 久久成人在线| 国产精品久久久久一区| 亚洲人成在线观看一区二区| 狠狠色综合播放一区二区| 中文av一区特黄| 91久久久久久国产精品| 欧美一区1区三区3区公司| 亚洲一区黄色| 欧美午夜电影网| 亚洲电影在线免费观看| 亚洲电影天堂av| 欧美在线观看视频在线| 午夜视频一区| 欧美日韩一区二区三区| 亚洲国产精品女人久久久| 一区二区三区在线视频免费观看 | 一本色道久久88综合日韩精品| 亚洲黄色在线| 欧美成人性网| 亚洲国产一区二区三区高清| 亚洲日韩中文字幕在线播放| 久久久久免费| 欧美高清视频一区| 亚洲精品一区二区三区99| 欧美精品久久一区| 一区二区不卡在线视频 午夜欧美不卡'| 亚洲美女在线国产| 欧美性色视频在线| 午夜久久久久久| 久久中文在线| 亚洲欧洲日本一区二区三区| 欧美精品免费播放| 亚洲天堂网站在线观看视频| 午夜日韩激情| 影音先锋日韩精品| 欧美精品电影在线| 亚洲综合成人婷婷小说| 久久精品一区二区三区不卡| 影音先锋日韩精品| 欧美欧美天天天天操| 亚洲小视频在线| 久久婷婷激情| 日韩视频在线免费观看| 国产精品第一区| 久久精品国产久精国产思思| 欧美大片一区二区三区| 在线一区二区日韩| 国产精品乱码一区二区三区| 久久国产精品久久久久久| 毛片av中文字幕一区二区| 日韩亚洲不卡在线| 国产伦理一区| 欧美成人精品在线观看| 亚洲精品一区二区在线| 午夜精品剧场| 国产亚洲精品一区二区| 免费看黄裸体一级大秀欧美| 亚洲视频精品| 欧美激情第1页| 亚洲欧美日韩专区| 亚洲黄色在线看| 国产精品视频免费| 免费视频一区| 久久精品国产精品| 一本一本久久| 亚洲国产色一区| 久久色中文字幕| 一本色道久久综合亚洲精品高清 | 久久久久久久精| 亚洲色图在线视频| 免费成人高清在线视频| 亚洲一区欧美二区| 亚洲人成7777| 激情综合电影网| 国产精品夫妻自拍| 欧美高清你懂得| 欧美在线观看视频在线| 在线亚洲一区观看| 亚洲日本va午夜在线电影| 久久综合久久美利坚合众国| 销魂美女一区二区三区视频在线| 91久久精品一区| 依依成人综合视频| 国产一在线精品一区在线观看| 欧美性大战久久久久| 欧美电影免费观看高清完整版| 欧美亚洲免费| 欧美一区二区三区视频在线观看| 99国产精品视频免费观看| 亚洲激情校园春色| 亚洲电影免费观看高清完整版在线| 久久精品免费电影| 久久国产精品免费一区| 久久大逼视频| 久久久97精品| 久久久久成人网| 久久在线91| 欧美电影专区| 亚洲高清一区二区三区| 欧美激情在线狂野欧美精品| 男人天堂欧美日韩| 欧美激情精品久久久久久变态| 蜜桃av一区| 亚洲第一精品久久忘忧草社区| 男人的天堂亚洲| 欧美激情精品久久久久久免费印度| 美女视频黄 久久| 亚洲高清自拍| 亚洲精品美女在线观看| 亚洲精选中文字幕| 宅男噜噜噜66国产日韩在线观看| 99国产精品国产精品久久| av72成人在线| 亚洲欧美日韩国产一区二区| 欧美一区二区在线免费播放| 久久精品亚洲精品| 噜噜爱69成人精品| 欧美日韩三区四区| 国产日韩欧美精品综合| 亚洲国产成人av在线| 日韩一级成人av| 亚洲欧美日韩国产成人| 性欧美大战久久久久久久久| 久久久91精品国产| 亚洲欧洲日本mm| 亚洲综合国产| 免费短视频成人日韩| 国产精品v欧美精品v日韩 | 欧美日韩高清在线播放| 国产欧美成人| 亚洲国产精品一区二区尤物区| 99re6热只有精品免费观看| 欧美一级艳片视频免费观看| 美女久久一区| 一区二区三区色| 久久久久久久久伊人| 欧美日韩免费一区二区三区| 国产亚洲免费的视频看| 亚洲国产三级网| 欧美在线你懂的| 亚洲麻豆国产自偷在线| 久久精品夜夜夜夜久久| 欧美日本在线一区| 国内精品久久久久久久影视蜜臀| 亚洲精选中文字幕| 久久久久www| 亚洲午夜精品久久久久久app| 日韩午夜剧场| 韩日精品视频一区| 亚洲一区二区三区乱码aⅴ蜜桃女| 久久久久久久久久久久久女国产乱| 久久欧美肥婆一二区| 一区二区三区日韩精品视频| 蜜桃av综合| 在线免费观看一区二区三区| 欧美在线你懂的| 国产精品99久久久久久久vr| 欧美精品久久99| 亚洲国产一区二区视频|