• <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 閱讀(174) 評論(0)  編輯 收藏 引用 所屬分類: B_搜索

            導航

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            热re99久久6国产精品免费| 91精品国产色综久久| 色老头网站久久网| 久久久亚洲裙底偷窥综合| 伊人久久大香线蕉av一区| 久久国产精品成人影院| 成人a毛片久久免费播放| 亚洲色欲久久久久综合网| 99久久精品免费看国产一区二区三区 | 久久e热在这里只有国产中文精品99| 久久精品国产72国产精福利| 国产69精品久久久久久人妻精品 | 久久夜色tv网站| 国内精品久久久久影院老司| 97久久久久人妻精品专区| 亚州日韩精品专区久久久| 91精品国产综合久久久久久| 亚洲色欲久久久久综合网 | 久久精品人人槡人妻人人玩AV | 久久99精品久久久大学生| 欧美一区二区精品久久| 国产成人精品久久| 久久亚洲av无码精品浪潮| 99re这里只有精品热久久 | 中文字幕一区二区三区久久网站| 久久这里都是精品| 久久国产热这里只有精品| 99久久777色| 久久久噜噜噜www成人网| 久久久久亚洲AV无码专区桃色| 大伊人青草狠狠久久| 97精品依人久久久大香线蕉97| 久久久无码精品亚洲日韩软件| 色综合久久久久| 久久91综合国产91久久精品| 久久亚洲精品中文字幕| 亚洲人成网亚洲欧洲无码久久| 综合久久一区二区三区 | 久久精品视频网| 国产午夜久久影院| 亚洲国产成人久久综合碰碰动漫3d |