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

隨筆-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>
            欧美精品一区二区三| 欧美在线视屏| 日韩午夜免费| 欧美四级电影网站| 亚洲自拍高清| 亚洲一区视频| 国产日韩欧美日韩| 亚洲免费成人av| 久久久久**毛片大全| 久久精品亚洲一区二区三区浴池| 国产精品嫩草99av在线| 久久久久久久久久久久久9999| 久久精品在线观看| 一区二区欧美日韩视频| 亚洲婷婷综合色高清在线| 国产亚洲欧美日韩美女| 亚洲高清免费在线| 男人插女人欧美| 午夜精品视频在线| 老鸭窝毛片一区二区三区| 中文在线资源观看视频网站免费不卡| 一区二区三区国产盗摄| 激情综合色综合久久| 亚洲三级电影在线观看| 国产亚洲精品7777| 亚洲免费观看在线观看| 极品日韩av| 在线视频中文亚洲| 亚洲日本中文字幕区 | 国产欧美日本一区视频| 免费成人av在线看| 国产精品黄视频| 亚洲成人资源| 狠狠色狠色综合曰曰| 日韩一级大片| 亚洲经典三级| 久久精品国产在热久久| 午夜伦理片一区| 欧美久色视频| 免费欧美日韩国产三级电影| 国产精品日韩在线播放| 亚洲黄色一区| 在线成人激情黄色| 欧美一区二区高清| 午夜日韩激情| 欧美视频二区36p| 亚洲国产一区在线| 久久av一区二区三区漫画| 亚洲女女女同性video| 中文在线资源观看视频网站免费不卡| 久久综合福利| 久久综合网络一区二区| 国产一区二区三区免费观看| 亚洲一区二区三区高清不卡| 在线亚洲自拍| 欧美日韩理论| 日韩视频欧美视频| 99这里只有精品| 你懂的视频一区二区| 欧美成人免费全部| 亚洲第一页自拍| 久久国产精品久久精品国产| 久久精品视频在线播放| 国产欧美日韩在线播放| 亚洲欧美久久久| 亚洲欧美视频一区| 国产精品尤物福利片在线观看| 亚洲网站视频| 久久福利电影| 激情视频亚洲| 免费在线欧美视频| 亚洲国产欧美一区二区三区丁香婷| 18成人免费观看视频| 男人的天堂亚洲在线| 91久久嫩草影院一区二区| 日韩天堂在线视频| 欧美精选一区| 在线亚洲一区| 久久久久久国产精品mv| 亚洲国产精品www| 欧美精品三级日韩久久| 一区二区不卡在线视频 午夜欧美不卡在| 中国女人久久久| 国产乱码精品1区2区3区| 久久久国产精品一区| 欧美激情亚洲国产| 亚洲在线日韩| 狠狠v欧美v日韩v亚洲ⅴ| 欧美成人一品| 亚洲天堂第二页| 狂野欧美性猛交xxxx巴西| 日韩手机在线导航| 国产亚洲欧美日韩日本| 久久久久国内| 亚洲国产日韩一区| 午夜久久电影网| 在线观看不卡| 国产精品高潮粉嫩av| 校园激情久久| 亚洲动漫精品| 欧美伊人久久大香线蕉综合69| 在线欧美亚洲| 国产精品国色综合久久| 免费一级欧美片在线播放| 亚洲视频欧美视频| 欧美国产欧美亚州国产日韩mv天天看完整| 日韩系列欧美系列| 国内成+人亚洲+欧美+综合在线| 欧美精品免费在线| 欧美一级片一区| 亚洲乱码久久| 欧美成年人视频网站| 欧美在线亚洲| 亚洲综合视频一区| 99国产精品| 国产欧美一区二区视频| 欧美视频在线观看免费网址| 久久亚洲精品中文字幕冲田杏梨| 一区二区三区蜜桃网| 亚洲国产精品久久久久秋霞影院| 午夜在线a亚洲v天堂网2018| 亚洲日本一区二区三区| 国产区精品视频| 国产精品美女一区二区| 欧美日韩理论| 欧美日韩国产成人在线观看| 久久亚洲精品网站| 欧美在线观看一二区| 亚洲一区免费| 亚洲视频免费在线| 99精品视频一区二区三区| 亚洲精品国久久99热| 你懂的国产精品| 玖玖玖国产精品| 久久久www成人免费毛片麻豆| 亚洲影院在线| 亚洲欧美日韩国产综合| 亚洲激情国产| 亚洲黑丝一区二区| 亚洲欧洲免费视频| 亚洲精品日本| 亚洲一区影音先锋| 午夜精品久久久久久久白皮肤 | 蜜臀av一级做a爰片久久| 久久精品人人| 久久一区二区三区国产精品 | 亚洲日本一区二区| 最新国产乱人伦偷精品免费网站| 欧美第十八页| 最新国产精品拍自在线播放| 亚洲国产成人av好男人在线观看| 亚洲第一综合天堂另类专| 欧美激情中文不卡| 亚洲伦理在线免费看| 一区二区三区四区精品| 亚洲免费视频中文字幕| 性欧美18~19sex高清播放| 久久精品99久久香蕉国产色戒| 久久精品国产清高在天天线 | 亚洲男女毛片无遮挡| 亚洲综合国产激情另类一区| 欧美在线免费| 美女网站久久| 欧美色欧美亚洲另类七区| 国产农村妇女毛片精品久久麻豆 | 亚洲麻豆视频| 西西人体一区二区| 美脚丝袜一区二区三区在线观看 | 蜜桃av一区二区| 欧美日韩福利在线观看| 国产精品免费福利| 在线视频观看日韩| 亚洲香蕉成视频在线观看| 欧美一区二区精品在线| 欧美成人午夜激情视频| 亚洲视频在线看| 六月天综合网| 国产精品欧美风情| 亚洲电影av| 一区二区三区日韩在线观看| 欧美一区日本一区韩国一区| 可以免费看不卡的av网站| 一本色道久久综合亚洲精品不卡| 午夜在线精品偷拍| 欧美视频一区二区三区在线观看| 国内精品久久久久久影视8 | 国产农村妇女精品| 9l国产精品久久久久麻豆| 久久亚洲美女| 亚洲无限av看| 销魂美女一区二区三区视频在线| 欧美成人视屏| 一区国产精品| 久久成人一区二区| 一区二区动漫| 欧美激情综合五月色丁香| 狠狠色丁香婷综合久久| 亚洲欧美日本日韩| 亚洲精选一区| 欧美1区3d|