• <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>

            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 閱讀(1195) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            久久国产综合精品五月天| 色婷婷狠狠久久综合五月| 欧美一区二区三区久久综合| 久久香综合精品久久伊人| 99久久99久久精品免费看蜜桃| 国产高潮久久免费观看| 日韩欧美亚洲综合久久| 夜夜亚洲天天久久| 伊人久久大香线蕉综合Av| 国产精品99久久久久久董美香| 色狠狠久久综合网| 伊人久久大香线蕉影院95| 亚洲а∨天堂久久精品9966| 久久国产精品77777| 欧美久久天天综合香蕉伊| 国产精品久久网| 97精品依人久久久大香线蕉97| 久久这里只精品国产99热| 亚洲精品午夜国产va久久| 66精品综合久久久久久久| 人妻无码αv中文字幕久久| 日韩久久无码免费毛片软件| 一本一道久久精品综合| 72种姿势欧美久久久久大黄蕉| 国产69精品久久久久观看软件| 成人精品一区二区久久| .精品久久久麻豆国产精品| 久久香综合精品久久伊人| 久久97久久97精品免视看| 日本福利片国产午夜久久| 久久久久成人精品无码中文字幕| 99久久国产亚洲综合精品| 亚洲va久久久久| 久久久久久久97| 亚洲va久久久久| 久久精品一区二区三区AV| 国产精品久久婷婷六月丁香| 国产精品久久久久久久app| 亚洲午夜久久久久妓女影院| 久久国产色av免费看| 亚洲国产精品无码久久一线|