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

coreBugZJ

此 blog 已棄。

To Miss Our Children Time, The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest

To Miss Our Children Time

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)

Problem Description
Do you remember our children time? When we are children, we are interesting in almost everything around ourselves. A little thing or a simple game will brings us lots of happy time! LLL is a nostalgic boy, now he grows up. In the dead of night, he often misses something, including a simple game which brings him much happy when he was child. Here are the game rules: There lies many blocks on the ground, little LLL wants build "Skyscraper" using these blocks. There are three kinds of blocks signed by an integer d. We describe each block's shape is Cuboid using four integers ai, bi, ci, di. ai, bi are two edges of the block one of them is length the other is width. ci is 
thickness of the block. We know that the ci must be vertical with earth ground. di describe the kind of the block. When di = 0 the block's length and width must be more or equal to the block's length and width which lies under the block. When di = 1 the block's length and width must be more or equal to the block's length which lies under the block and width and the block's area must be more than the block's area which lies under the block. When di = 2 the block length and width must be more than the block's length and width which lies under the block. Here are some blocks. Can you know what's the highest "Skyscraper" can be build using these blocks?
 

Input
The input has many test cases. 
For each test case the first line is a integer n ( 0< n <= 1000) , the number of blocks. 
From the second to the n+1'th lines , each line describing the i‐1'th block's a,b,c,d (1 =< ai,bi,ci <= 10^8 , d = 0 or 1 or 2). 
The input end with n = 0.
 

Output
Output a line contains a integer describing the highest "Skyscraper"'s height using the n blocks.
 

Sample Input
3
10 10 12 0
10 10 12 1
10 10 11 2
2
10 10 11 1
10 10 11 1
0
 

Sample Output
24
11
 


先排序,然后動態規劃,dp[ i ] 表示以第 i 個長方體放在頂上的最大高度。
注意長寬相乘使用32位整數會溢出。


 1 #include <iostream>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 typedef  int  I32;
 7 typedef  long long  I64;
 8 
 9 struct Block
10 {
11          I64 a, b, c, d;
12 };
13 
14 bool operator<const Block &a, const Block &b ) {
15         return (  (a.a  < b.a) || 
16                  ((a.a == b.a)&&(a.b  < b.b)) || 
17                  ((a.a == b.a)&&(a.b == b.b)&&(a.d > b.d))
18                );
19 }
20 
21 const I32 N = 1009;
22 
23 I64    dp[ N ];
24 Block  bk[ N ];
25 
26 int main() {
27         I32 n, i, j;
28         I64 ans, t;
29         for ( ; ; ) {
30                 cin >> n;
31                 if ( n < 1 ) {
32                         break;
33                 }
34                 for ( i = 1; i <= n; ++i ) {
35                         cin >> bk[ i ].a >> bk[ i ].b >> bk[ i ].c >> bk[ i ].d;
36                         if ( bk[ i ].a < bk[ i ].b ) {
37                                 t = bk[ i ].a;
38                                 bk[ i ].a = bk[ i ].b;
39                                 bk[ i ].b = t;
40                         }
41                 }
42                 sort( bk+1, bk+n+1 );
43 
44                 for ( i = 1; i <= n; ++i ) {
45                         dp[ i ] = bk[ i ].c;
46                 }
47                 for ( i = 2; i <= n; ++i ) {
48                         switch ( bk[ i ].d ) {
49                         case 0 : 
50                                 for ( j = 1; j < i; ++j ) {
51                                         if ( (bk[j].a<=bk[i].a) && 
52                                              (bk[j].b<=bk[i].b) && 
53                                              (dp[j]+bk[i].c>dp[i]) 
54                                            ) {
55                                                 dp[ i ] = dp[ j ] + bk[ i ].c;
56                                         }
57                                 }
58                                 break;
59                         case 1 : 
60                                 for ( j = 1; j < i; ++j ) {
61                                         if ( (bk[j].a<=bk[i].a) && 
62                                              (bk[j].b<=bk[i].b) && 
63                                              (bk[j].a*bk[j].b < bk[i].a*bk[i].b) && 
64                                              (dp[j]+bk[i].c>dp[i]) 
65                                            ) {
66                                                 dp[ i ] = dp[ j ] + bk[ i ].c;
67                                         }
68                                 }
69                                 break;
70                         case 2 : 
71                                 for ( j = 1; j < i; ++j ) {
72                                         if ( (bk[j].a<bk[i].a) && 
73                                              (bk[j].b<bk[i].b) && 
74                                              (dp[j]+bk[i].c>dp[i]) 
75                                            ) {
76                                                 dp[ i ] = dp[ j ] + bk[ i ].c;
77                                         }
78                                 }
79                                 break;
80                         }
81                 }
82 
83                 ans = dp[ 1 ];
84                 for ( i = 2; i <= n; ++i ) {
85                         if ( ans < dp[ i ] ) {
86                                 ans = dp[ i ];
87                         }
88                 }
89 
90                 cout << ans << endl;
91         }
92         return 0;
93 }
94 

posted on 2011-09-03 18:24 coreBugZJ 閱讀(1205) 評論(0)  編輯 收藏 引用 所屬分類: ACM

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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香蕉一区二区| 日韩系列欧美系列| 久久精品亚洲精品| 国精品一区二区三区| 久久伊人亚洲| 欧美成人一区二区三区片免费| 亚洲精品在线观看视频| 妖精视频成人观看www| 国产精品私房写真福利视频 | 欧美日韩一区二区欧美激情| 亚洲婷婷综合色高清在线| 亚洲已满18点击进入久久| 国产一区二区三区在线观看网站 | 一区二区三区高清视频在线观看 | 亚洲福利视频三区| 欧美日韩视频| 久久久久亚洲综合| 欧美日韩国产成人在线91| 欧美一区二区成人6969| 久久久噜噜噜久久久| 在线亚洲美日韩| 久久国产手机看片| 在线一区二区三区四区五区| 久久成人免费视频| av成人手机在线| 久久国产精品久久精品国产| 日韩一区二区精品在线观看| 欧美亚洲一区二区在线观看| 艳女tv在线观看国产一区| 午夜国产精品视频| 亚洲美女精品久久| 久久国产直播| 午夜精彩视频在线观看不卡 | 久久久福利视频| 亚洲一区二区精品视频| 久久久久这里只有精品| 午夜在线成人av| 欧美黄色免费网站| 蜜臀91精品一区二区三区| 国产精品第一区| 亚洲欧洲综合| 亚洲国产成人不卡| 欧美在线播放| 欧美一区二区三区在线看| 欧美日韩亚洲一区二区三区四区| 老司机午夜精品视频| 国产日韩精品久久久| 一本色道久久综合亚洲精品不| 亚洲国产精品黑人久久久| 久久精品国产99精品国产亚洲性色| 亚洲永久免费精品| 欧美日韩在线电影| 亚洲欧洲日本在线| 亚洲精品网址在线观看| 老司机精品福利视频| 久热精品视频在线观看| 国产一区二区精品久久99| 西瓜成人精品人成网站| 欧美一区二区三区喷汁尤物| 欧美体内谢she精2性欧美| 一本色道久久88亚洲综合88| 亚洲视频axxx| 欧美午夜片在线免费观看| aa亚洲婷婷| 欧美一级艳片视频免费观看| 国产精品综合色区在线观看| 午夜精品视频| 老司机午夜精品视频在线观看| 狠狠综合久久av一区二区老牛| 欧美专区亚洲专区| 欧美高清在线视频| 亚洲伦伦在线| 欧美日韩国产高清视频| 这里只有精品电影| 欧美在线视频二区| 亚洲福利视频二区| 欧美激情一区二区三区全黄 | 欧美一区二区三区免费在线看| 欧美中文在线观看| 在线观看日韩国产| 欧美精品一区二区在线播放| 一本色道久久综合狠狠躁的推荐| 午夜精品免费在线| 国模精品一区二区三区| 免费欧美日韩| 一区二区三区四区五区在线| 久久精品人人爽| 亚洲精品乱码久久久久久黑人 | 欧美黄色免费| 亚洲在线视频| 欧美大尺度在线| 亚洲一区二区三区午夜| 国产午夜亚洲精品羞羞网站 | 欧美日韩精品二区| 亚洲欧美在线视频观看| 欧美激情片在线观看| 亚洲欧美国产高清va在线播| 激情一区二区| 欧美日韩综合不卡| 久久人人爽人人| 亚洲午夜性刺激影院| 免费亚洲电影| 欧美一区二区三区免费大片| 亚洲欧洲一区| 国产一区二区三区在线观看网站| 欧美国产在线电影| 欧美在线一区二区| 一本大道av伊人久久综合| 毛片一区二区三区| 午夜精品成人在线| 99re热精品| 亚洲第一黄色| 国产一区二区三区精品久久久| 欧美黑人多人双交| 老司机精品久久| 亚洲欧洲99久久| 在线亚洲伦理| 亚洲精品美女久久久久| 免费日韩av片| 久久中文欧美| 久久精品日产第一区二区三区| 亚洲一级二级在线| 亚洲乱码视频| 亚洲精品久久久久久下一站| 影音先锋国产精品| 国产午夜精品久久久久久免费视| 国产精品99一区| 欧美日韩国产一区二区三区| 欧美a级片网站| 久久综合精品一区| 久久久综合网| 久久午夜精品一区二区| 久久久精彩视频| 久久精品观看| 久久久免费精品视频| 久久精品夜色噜噜亚洲a∨| 午夜电影亚洲| 欧美在线免费一级片| 欧美一区亚洲| 久久精品一区蜜桃臀影院 | 亚洲精品视频中文字幕| 亚洲激情电影在线| 亚洲国产综合在线看不卡| 亚洲成人在线网站| 亚洲精品久久久久久久久| 亚洲国产精品视频一区| 亚洲日本理论电影| 99精品国产高清一区二区| 一区二区三区欧美亚洲| 亚洲午夜激情| 欧美在线一区二区| 噜噜噜躁狠狠躁狠狠精品视频| 免费观看亚洲视频大全| 欧美大学生性色视频| 欧美日韩一区在线观看| 国产精品毛片大码女人| 国产一区日韩欧美| 亚洲国产精品第一区二区| 日韩亚洲一区在线播放| 亚洲在线网站| 久久中文欧美| 亚洲裸体视频| 性欧美暴力猛交69hd| 久久在线免费观看| 欧美日韩国产成人高清视频| 国产精品久久久亚洲一区| 国产主播喷水一区二区| 亚洲国产第一页| 亚洲伊人色欲综合网| 久久夜精品va视频免费观看| 亚洲狠狠婷婷| 亚洲欧美日本另类| 嫩草国产精品入口| 国产精品稀缺呦系列在线| 一区二区三区在线不卡| 亚洲天堂成人| 欧美成人精品h版在线观看| 亚洲久久在线| 久久久免费精品| 国产精品黄视频| 亚洲激情av| 久久久999精品免费| 日韩午夜免费视频| 狂野欧美激情性xxxx欧美| 国产精品视频成人| 日韩一区二区福利| 麻豆91精品91久久久的内涵| 在线亚洲欧美专区二区| 免费的成人av| 国产亚洲一区二区在线观看| 日韩一区二区久久| 欧美成人中文字幕在线| 午夜免费日韩视频| 欧美视频导航| 99re6这里只有精品视频在线观看| 久久久久国产精品午夜一区| 亚洲午夜91| 欧美三级日韩三级国产三级 | 国产精品电影观看| 99re6热在线精品视频播放速度|