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

            堅信:勤能補拙

            PKU 1010 STAMPS

            問題:
            http://poj.org/problem?id=1010

            思路:
            題目比較難理解,解題的話就是DFS
            整整花了我一個晚上,終于AC了,(*^__^*) 嘻嘻……
            雖然時間花了挺久,雖然自己的解法時間需要500+MS,雖然存在其他更優的解法,雖然......,但還是相當有成就感,完全是我自己寫出來的
            如果這題放在5個月之前,估計完全不知道怎么去寫
            在沒AC之前,我一直想著自己還是原來那么菜,現在,至少可以說,比5個月之前的我已經強了
            繼續努力,Fighting...

            代碼:
              1 /* 388K 547MS */
              2 #include<stdio.h>
              3 #include<string.h>
              4 #include<stdlib.h>
              5 #define MAX_LEN 65 /* maximum number of different types of stamps */
              6 #define UPPER 4 /* maximum number of stamps */
              7 int types, stamps[MAX_LEN];
              8 int request;
              9 int maxdf, minusd, high, tie, exist, mark[MAX_LEN], ans[MAX_LEN];
             10 
             11 int
             12 compare(const void *arg1, const void *arg2)
             13 {
             14     return (*(int *)arg1)-(*(int *)arg2);
             15 }
             16 
             17 void
             18 output()
             19 {
             20     int i, j;
             21     if(!exist) {
             22         printf("%d ---- none\n", request);
             23         return;
             24     }
             25     printf("%d (%d): ", request, maxdf);
             26     if(tie)
             27         printf("tie\n");
             28     else {
             29         for(i=0; i<types; i++
             30             for(j=0; j<ans[i]; j++)
             31                 printf("%d ", stamps[i]);
             32         printf("\n");
             33     }
             34 }
             35 
             36 void
             37 dfs(int remain, int index, int curdf, int curusd, int curhigh)
             38 {
             39     int i, flag = 0;
             40     if(remain == 0) {
             41         if(curdf < maxdf)
             42             return;
             43         /* satisfy the conditions: UPDATE */
             44         if((curdf>maxdf) || (curdf==maxdf&&curusd<minusd) || (curdf==maxdf&&curusd==minusd&&curhigh>high)) {
             45             maxdf = curdf;
             46             minusd = curusd;
             47             high = curhigh;
             48             exist = 1;
             49             tie = 0/* remember reset 'tie' */
             50             memcpy(ans, mark, sizeof(int)*MAX_LEN); /* copy the current best to 'ans' */
             51             return;
             52         }
             53         /* TIE occurred */
             54         if(curdf==maxdf && curusd==minusd && curhigh==high) {
             55             tie = 1;
             56             return;
             57         }
             58         return;
             59     }
             60     /* still exist several stamps unmarked */
             61     for(i=index; i<types; i++) { /* Attention: i starts from 'index', which avoid duplicates such as '1 3' and '3 1' */
             62         if(!mark[i] && stamps[i]<=remain && curusd+1<=UPPER) {
             63             ++mark[i];
             64             flag = 1;
             65             dfs(remain-stamps[i], i+1, curdf+1, curusd+1, stamps[i]);
             66             --mark[i];
             67         }
             68     }
             69     /* all available stamps have been marked */
             70     if(!flag) {
             71         for(i=types-1; i>=0; i--) {
             72             if(stamps[i]<=remain && curusd+1<=UPPER) {
             73                 ++mark[i];
             74                 dfs(remain-stamps[i], 0, curdf, curusd+1, curhigh);
             75                 --mark[i];
             76             }
             77         }
             78     }
             79 }
             80 
             81 int
             82 main(int argc, char **argv)
             83 {
             84     while(1) {
             85         types = 0;
             86         if(scanf("%d"&stamps[types]) == EOF)
             87             break;
             88         ++types;
             89         while(scanf("%d"&stamps[types]) && stamps[types])
             90             ++types;
             91         qsort(stamps, types, sizeof(int), compare); /* ascent order */
             92 
             93         while(scanf("%d"&request) && request) { /* each request */
             94             maxdf = high = 0;
             95             minusd = MAX_LEN+1;
             96             exist = tie = 0;
             97             memset(mark, 0sizeof(mark));
             98             dfs(request, 0000);
             99             output();
            100         }
            101     }
            102     return 0;
            103 }

            posted on 2010-10-22 00:38 simplyzhao 閱讀(311) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導航

            <2010年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲精品乱码久久久久久按摩| 国产免费久久久久久无码| 久久综合狠狠色综合伊人| 久久超乳爆乳中文字幕| 天天久久狠狠色综合| 久久se精品一区二区影院 | 一本色道久久综合狠狠躁篇| 2021国产精品久久精品| 久久久精品人妻一区二区三区蜜桃 | 少妇久久久久久被弄到高潮| 国产精品久久久久久搜索| 少妇熟女久久综合网色欲| 久久久久久久97| 久久亚洲国产精品123区| 久久国产成人| 99久久国语露脸精品国产| 亚洲综合久久久| 久久久久亚洲AV成人网人人软件| 久久久久99精品成人片欧美 | 久久精品国产69国产精品亚洲| 国产美女亚洲精品久久久综合| 亚洲国产高清精品线久久| 亚洲精品高清国产一久久| 久久这里只精品国产99热| 亚洲第一极品精品无码久久| 亚洲精品国产第一综合99久久| 精品熟女少妇aⅴ免费久久| 久久夜色精品国产噜噜麻豆| 久久er99热精品一区二区| 久久天天躁夜夜躁狠狠| 一本色道久久综合狠狠躁| 久久成人永久免费播放| 国内精品久久久久影院网站| 色综合合久久天天综合绕视看| 久久久久免费看成人影片| 99久久精品免费看国产一区二区三区| 久久久久久一区国产精品| 久久久久亚洲AV成人网人人网站| 久久精品无码专区免费 | 综合久久国产九一剧情麻豆| 久久丫忘忧草产品|