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

            A Za, A Za, Fighting...

            堅信:勤能補拙

            USACO Packing Rectangles

            問題:
            http://ace.delos.com/usacoprob2?a=CTINrbaHwEW&S=packrec

            思路:
            這題不會,考慮的時候以為任意兩個矩陣至少存在相同的邊才可以合并...結果完全錯誤

            參考:
            http://starforever.blog.hexun.com/2097115_d.html
            http://greenmoon55.com/usaco-packing-rectangles/

            另外,這題學會了在C里面使用bool類型,原來不知道呢(*^__^*) 嘻嘻……
            stdbool.h頭文件

            代碼:
              1 /*
              2 ID: simplyz2
              3 LANG: C
              4 TASK: packrec
              5 */
              6 #include<stdio.h>
              7 #include<stdbool.h>
              8 #include<stdlib.h>
              9 #include<string.h>
             10 #define MAX_NUM 5
             11 #define INF 0x7FFFFFFF
             12 #define Max(a, b) ((a)>(b) ? (a) : (b))
             13 struct Rec {
             14     int h, w;
             15 } rectangle[MAX_NUM], rect[MAX_NUM], ans[MAX_NUM];
             16 bool used[MAX_NUM];
             17 int w, h, total, area;
             18 
             19 void
             20 exchange(struct Rec *r)
             21 {
             22     int temp = r->h;
             23     r->= r->w;
             24     r->= temp;
             25 }
             26 
             27 void
             28 judge()
             29 {
             30     int i, j, temp;
             31     if(w > h) {
             32         temp = w;
             33         w = h;
             34         h = temp;
             35     }
             36     if(w*<= area) {
             37         if(w*== area) {
             38             for(i=1; i<total; i++)
             39                 if(ans[i].w == w)
             40                     return;
             41             for(i=1; i<total; i++)
             42                 if(ans[i].w > w) {
             43                     for(j=total; j>i; j--)
             44                         ans[j] = ans[j-1];
             45                     ans[i].w = w;
             46                     ans[i].h = h;
             47                     ++total;
             48                     return;
             49                 }
             50             ans[total].w = w;
             51             ans[total++].h = h;
             52         } else {
             53             area = w*h;
             54             total = 1;
             55             ans[total].w = w;
             56             ans[total].h = h;
             57         }
             58     }
             59 }
             60 
             61 void
             62 work()
             63 {   
             64     //Case 1
             65     w=rect[1].w+rect[2].w+rect[3].w+rect[4].w;
             66     h=Max(rect[1].h,rect[2].h);
             67     h=Max(h,rect[3].h);
             68     h=Max(h,rect[4].h);
             69     judge();
             70  
             71     //Case 2
             72     w=Max(rect[1].w+rect[2].w+rect[3].w,rect[4].w);
             73     h=Max(rect[1].h,rect[2].h);
             74     h=Max(h,rect[3].h);
             75     h+=rect[4].h;
             76     judge();
             77  
             78     //Case 3
             79     w=Max(rect[1].w+rect[2].w,rect[3].w)+rect[4].w;
             80     h=Max(Max(rect[1].h,rect[2].h)+rect[3].h,rect[4].h);
             81     judge();
             82  
             83     //Case 4
             84     w=rect[1].w+Max(rect[2].w,rect[3].w)+rect[4].w;
             85     h=Max(rect[1].h,rect[4].h);
             86     h=Max(h,rect[2].h+rect[3].h);
             87     judge();
             88  
             89     //Case 6
             90     if (rect[3].h>=rect[2].h+rect[4].h)
             91     {
             92         w=Max(rect[3].w+rect[2].w,rect[3].w+rect[4].w);
             93         w=Max(w,rect[1].w);
             94         h=rect[1].h+rect[3].h;
             95         judge();
             96         return;
             97     }
             98     if (rect[3].h>rect[4].h)
             99     {
            100         w=Max(rect[1].w+rect[2].w,rect[2].w+rect[3].w);
            101         w=Max(w,rect[4].w+rect[3].w); 
            102         h=Max(rect[1].h+rect[3].h,rect[2].h+rect[4].h);
            103         judge();
            104         return;
            105     }
            106     if (rect[3].h==rect[4].h)
            107     {
            108         w=Max(rect[1].w+rect[2].w,rect[3].w+rect[4].w);
            109         h=Max(rect[1].h,rect[2].h)+rect[3].h;
            110         judge();
            111         return;
            112     }
            113     if (rect[3].h<rect[4].h && rect[4].h<rect[3].h+rect[1].h)
            114     {
            115         w=Max(rect[1].w+rect[2].w,rect[1].w+rect[4].w);
            116         w=Max(w,rect[3].w+rect[4].w);
            117         h=Max(rect[1].h+rect[3].h,rect[2].h+rect[4].h);
            118         judge();
            119         return;
            120     }
            121     w=Max(rect[2].w,rect[1].w+rect[4].w);
            122     w=Max(w,rect[3].w+rect[4].w);
            123     h=rect[4].h+rect[2].h;
            124     judge(); 
            125 }
            126 
            127 void
            128 rotate(int depth)
            129 {
            130     if(depth == MAX_NUM) {
            131         work();
            132         return;
            133     }
            134     rotate(depth+1);
            135     exchange(rect+depth);
            136     rotate(depth+1);
            137 }
            138 
            139 void
            140 dfs(int depth)
            141 {
            142     int i;
            143     if(depth == MAX_NUM) {
            144         rotate(1);
            145         return;
            146     }
            147     for(i=1; i<MAX_NUM; i++) {
            148         if(!used[i]) {
            149             used[i] = true;
            150             rect[depth] = rectangle[i];
            151             dfs(depth+1);
            152             used[i] = false;
            153         }
            154     }
            155 }
            156 
            157 int
            158 main(int argc, char **argv)
            159 {
            160     int i;
            161     freopen("packrec.in""r", stdin);
            162     freopen("packrec.out""w", stdout);
            163     for(i=1; i<MAX_NUM; i++)
            164         scanf("%d %d"&rectangle[i].w, &rectangle[i].h);
            165     total = 1;
            166     area = INF;
            167     memset(used, 0sizeof(used));
            168     dfs(1);
            169     printf("%d\n", area);
            170     for(i=1; i<total; i++)
            171         printf("%d %d\n", ans[i].w, ans[i].h);
            172     return 0;
            173 }

            posted on 2010-10-13 19:45 simplyzhao 閱讀(392) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導航

            <2010年6月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产AV影片久久久久久| 久久99精品国产自在现线小黄鸭| 性欧美大战久久久久久久久| 国产精品久久久亚洲| 九九久久99综合一区二区| 久久影院亚洲一区| 99国产精品久久| 久久亚洲精品成人无码网站| 91精品国产9l久久久久| 久久九色综合九色99伊人| 亚洲成色999久久网站| 久久精品国产亚洲AV无码娇色| 热综合一本伊人久久精品| 色综合久久天天综合| 国产精品久久久久久福利漫画| 久久国产影院| 奇米综合四色77777久久| 午夜人妻久久久久久久久| 国产L精品国产亚洲区久久| 久久99久国产麻精品66| 精品多毛少妇人妻AV免费久久 | 国产成人精品久久亚洲| 2021最新久久久视精品爱| 久久天天日天天操综合伊人av| 丁香五月网久久综合| 日韩人妻无码精品久久免费一 | 久久人人爽爽爽人久久久| 无码乱码观看精品久久| 国产免费久久久久久无码| 久久精品成人免费看| 久久超乳爆乳中文字幕| 东方aⅴ免费观看久久av| 99re久久精品国产首页2020| 一本色道久久88—综合亚洲精品 | 色播久久人人爽人人爽人人片aV| 日本免费久久久久久久网站| 狠色狠色狠狠色综合久久| 精品国产91久久久久久久| 久久天堂电影网| 久久国产精品波多野结衣AV| 久久久久久久女国产乱让韩|