• <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 1416 Shredding Company

            問題:
            http://acm.pku.edu.cn/JudgeOnline/problem?id=1416

            思路:
            深度優先搜索,找出所有可能的劃分,并適當減枝
            這里搜索的對象是什么?
            我的第一個想法受到了前幾天完成PKU 1950的啟發,對于從高到低的每一位,有兩種可能:
            a. 作為解的一部分,加入總和
            b. 不加入總和,而是作為向下繼續搜索時的高位
            dfs(depth, cur_sum, pre)
            depth: 搜索深度
            cur_sum: 當前總和
            pre: 保留位
            經過一段時間的調試,一次AC了
            存在的問題是:  對于每一種可能的解都會重復記錄兩次,例如:
            輸入 376  144139
            輸出 283  144  139
            dfs(6, 283, 0)與dfs(6, 144, 139)都可以得到該解

            之后,查看了網上的代碼,原來不用想的這么復雜
            對于第k位,我們搜索從其開始的所有可能,然后遞歸,例如:
            對于將被“粉碎"的12346,對于第一位'1',可能的劃分有1, 12, 123, 1234, 12346

            代碼(方法一):
             1 #define MAX_LEN 7
             2 int target, num;
             3 int digits_count, digits[MAX_LEN];
             4 int sum_count, sum, parts_count, parts[MAX_LEN];
             5 int ans_count, ans[MAX_LEN];
             6 
             7 void
             8 init()
             9 {
            10     int i, temp, rem;
            11     memset(digits, -1sizeof(digits));
            12     memset(parts, -1sizeof(parts));
            13     digits_count = sum_count = parts_count = 0;
            14     sum = -1;
            15     rem = num;
            16     do {
            17         digits[digits_count++= rem % 10;
            18         rem /= 10;
            19     } while(rem!=0);
            20     for(i=0; i<digits_count/2; i++) {
            21         temp = digits[i];
            22         digits[i] = digits[digits_count-i-1];
            23         digits[digits_count-i-1= temp;
            24     }
            25 }
            26 
            27 void
            28 dfs(depth, cur_sum, pre)
            29 {
            30     if(cur_sum+pre>target) /* pruning */
            31         return;
            32     //printf("dfs(%d, %d, %d)\n", depth, cur_sum, pre);
            33     if(depth == digits_count) {
            34         if(pre != 0) {
            35             parts[parts_count++= pre;
            36             cur_sum += pre;
            37         }
            38         if(cur_sum == sum)
            39             ++sum_count;
            40         if(cur_sum > sum) {
            41             sum = cur_sum;
            42             sum_count = 1;
            43             ans_count = parts_count;
            44             memcpy(ans, parts, sizeof(int)*ans_count);
            45         }
            46         if(pre != 0)
            47             parts[parts_count--= -1;
            48         return;
            49     }
            50     /* branch 1 */
            51     parts[parts_count++= digits[depth] + pre * 10;
            52     dfs(depth+1, cur_sum+parts[parts_count-1], 0);
            53     parts[parts_count--= -1;
            54     /* branch 2 */
            55     dfs(depth+1, cur_sum, pre*10+digits[depth]);
            56 }

            代碼(方法二):
             1 #define MAX_LEN 7
             2 int target, len;
             3 char num[MAX_LEN];
             4 int sum_count, sum, parts_count, parts[MAX_LEN];
             5 int ans_count, ans[MAX_LEN];
             6 
             7 void
             8 dfs(int depth, int cur_sum)
             9 {
            10     int i, value = 0;
            11     if(cur_sum > target) /* pruning */
            12         return;
            13     if(depth == len) {
            14         if(cur_sum == sum)
            15             ++sum_count;
            16         if(cur_sum > sum) {
            17             sum = cur_sum;
            18             sum_count = 1;
            19             ans_count = parts_count;
            20             memcpy(ans, parts, sizeof(int)*ans_count);
            21         }
            22         return;
            23     }
            24     for(i=depth; i<len; i++) {
            25         value *= 10;
            26         value += (num[i]-'0');
            27         parts[parts_count++= value;
            28         dfs(i+1, cur_sum+value);
            29         parts[parts_count--= -1;
            30     }
            31 }

            posted on 2010-07-27 17:51 simplyzhao 閱讀(175) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導航

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久九九亚洲精品| 久久久久久夜精品精品免费啦| 国产精品成人精品久久久| 久久久噜噜噜久久| 亚洲精品无码久久久久去q| 久久精品国产99国产电影网| 久久久久亚洲AV无码专区网站| 无码人妻久久一区二区三区| 色综合色天天久久婷婷基地| 伊人久久大香线蕉综合5g| 国产美女久久久| 久久久久久久精品成人热色戒 | 亚洲国产日韩欧美久久| 亚洲AV日韩精品久久久久| 久久99精品久久久久久齐齐| 日韩精品久久无码中文字幕| 久久综合九色综合久99| 国产精品九九九久久九九| 亚洲国产精品一区二区久久hs| 99久久精品免费国产大片| 午夜天堂精品久久久久| 色天使久久综合网天天| 亚洲AV伊人久久青青草原| 久久青青草原综合伊人| 精品久久久久久无码专区不卡 | 久久久久高潮综合影院| 国内精品久久久久久久久| 精品午夜久久福利大片| 久久精品国产亚洲av麻豆小说 | 欧美噜噜久久久XXX| 99久久综合国产精品免费| 久久无码人妻精品一区二区三区| 国产V亚洲V天堂无码久久久| 人妻无码αv中文字幕久久| 中文字幕热久久久久久久| 色妞色综合久久夜夜| 亚州日韩精品专区久久久| 超级97碰碰碰碰久久久久最新| 亚洲精品tv久久久久| 日韩欧美亚洲国产精品字幕久久久| 亚洲欧美精品伊人久久|