青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

ACM搜索題經(jīng)典 Sticks

/*
EOJ  1981 Sticks
POJ  1011 Sticks
HDOJ 1455 Sticks
UVA  307  Sticks


----問題描述：

George took sticks of the same length and cut them randomly until all parts became at most 50 units long.
Now he wants to return sticks to the original state, but he forgot how many sticks he had originally


----輸入：

The input contains blocks of 2 lines.
The first line contains the number of sticks parts after cutting, there are at most 64 sticks.
The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.


----輸出：

The output should contains the smallest possible length of original sticks, one per line.


----樣例輸入：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0


----樣例輸出：

6
5


----分析：

從短到長枚舉原始木棍長度，然后嘗試能否拼裝成功，
第一次嘗試成功時的原始木棍長度，即為答案。

嘗試方法，為深度優(yōu)先搜索，具體剪枝策略見代碼注釋。


----幾組比較強(qiáng)的測試數(shù)據(jù)：

input

64
40 40 30 35 35 26 15 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40 40 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40 40
64
40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40
64
33 36 7 45 6 14 14 14 28 39 35 36 5 33 21 32 29 37 31 3 2 19 40 34 25 1 33 49 20 14 25 36 45 37 47 28 39 8 36 44 8 48 41 1 13 18 9 10 34 42 41 39 42 20 23 6 40 28 49 16 38 33 15 7

output

454
1251
81

*/



/**********************************************************
版本三：
EOJ  1981   0MS  231K
POJ  1011  16MS  164K
HDOJ 1455   0MS  200K
UVA  307   WA

增加搜索次數(shù)限制。

（UVA 上加此限制則 WA，否則 0.212 AC，見版本二）
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define  L  70

int cutnum;                 // 木棍的數(shù)量
int cutlen[ L ], totlen;    // 木棍的各自長度，及總長度

int cmp( const void *pa, const void *pb) {
        return (*((int*)pb)) - (*((int*)pa));
}

int orglen, orgnum; // 原始木棍的長度及其數(shù)量
int used[ L ];      // dfs 時標(biāo)記某木棍是否已經(jīng)被用于組裝原始木棍
//int choice[ L ];

// 若搜索次數(shù)超過此值，則認(rèn)為不可能成功
#define  LIM  100000
int lim;
        // 嘗試拼裝某原始木棍，
        // 此次嘗試之前，
        // 已經(jīng)使用了 t 根木棍，
        // 已經(jīng)拼裝出了原始木棍的部分長度，剩余 c 長度需要拼裝，
        // 此次嘗試，只需要從第 b 根木棍開始。
int dfs(int c, int b, int t) {
        int i, prelen = -1;
        if ( --lim <= 0 ) {
                return 0;
        }
        if ( 0 == c ) {
                // 剩余長度為 0，則開始拼裝下一根原始木棍，
                // 需擴(kuò)大嘗試的范圍。
                for ( i = 0; (i < cutnum) && (used[i]); ++i ) {
                }
                // 所有木棍都已經(jīng)被用于拼裝原始木棍，
                // 即嘗試成功。
                if ( i >= cutnum ) {
                        //printf("i >= cutnum, t = %d\n", t);
                        return 1;
                }
                used[ i ] = 1;
                //choice[ t ] = i;
                // 任一原始木棍中，必含有剩余木棍中最長的那根
                if ( dfs(orglen-cutlen[i], i+1, t+1) ) {
                        return 1;
                }
                used[ i ] = 0;
                return 0;
        }
        for ( i = b; i < cutnum; ++i ) {
                if (    (used[ i ]) ||          // 木棍沒用過
                        (c < cutlen[i]) ||      // 剩余長度能容納此木棍
                        (prelen == cutlen[i])   // 此長度的木棍已經(jīng)試過，不行，無需再試
                ) {
                        continue;
                }
                used[ i ] = 1;
                //choice[ t ] = i;

                // 下次嘗試從后面的木棍開始，前面的木棍無需考慮
                if ( dfs(c-cutlen[i], i+1, t+1) ) {
                        return 1;
                }

                prelen = cutlen[ i ];

                used[ i ] = 0;

                // 存在一木棍剛好可以符合剩余長度，則不再嘗試其它
                if ( c == cutlen[ i ] ) {
                        return 0;
                }
        }
        return 0;
}

int find(){
        // 原始木棍長度必為總長度的約數(shù)
        if ( 0 != totlen % orglen ) {
                return 0;
        }
        orgnum = totlen / orglen;
        memset(used, 0, sizeof(used));
        lim = LIM;
        return dfs(0, 0, 0);
}

int main() {
        int i;
        while ( (1 == scanf("%d", &cutnum)) && (0 < cutnum) ) {
                totlen = 0;
                for ( i = 0; i < cutnum; ++i ) {
                        scanf("%d", cutlen+i);
                        totlen += cutlen[ i ];
                }
                // 將木棍從長到短排序，然后從長到短搜索之
                qsort(cutlen, cutnum, sizeof(cutlen[0]), cmp);

                /*for ( i = 0; i < cutnum; ++i ) {
                        printf("-%d-", cutlen[ i ]);
                }
                printf("\n");*/

                // 原始木棍長度必大于等于最長木棍長度，
                // 小于等于木棍總長度，
                // 從短到長枚舉原始木棍長度。
                for ( orglen = cutlen[0]; (orglen < totlen) && (! find()); ++orglen ) {
                }
                printf("%d\n", orglen);
                //if ( orglen != totlen ) {
                //        for ( i = 0; i < cutnum; ++i ) {
                //                printf("--%d--", choice[ i ]);
                //        }
                //        printf("\n");
                //}
        }
        return 0;
}


/**********************************************************
版本二：
EOJ  1981  TLE
POJ  1011  0MS   164K
HDOJ 1455  0MS   188K
UVA  307   0.212
*/
/*
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define  L  70

int cutnum;                 // 木棍的數(shù)量
int cutlen[ L ], totlen;    // 木棍的各自長度，及總長度

int cmp( const void *pa, const void *pb) {
        return (*((int*)pb)) - (*((int*)pa));
}

int orglen, orgnum; // 原始木棍的長度及其數(shù)量
int used[ L ];      // dfs 時標(biāo)記某木棍是否已經(jīng)被用于組裝原始木棍
//int choice[ L ];

        // 嘗試拼裝某原始木棍，
        // 此次嘗試之前，
        // 已經(jīng)使用了 t 根木棍，
        // 已經(jīng)拼裝出了原始木棍的部分長度，剩余 c 長度需要拼裝，
        // 此次嘗試，只需要從第 b 根木棍開始。
int dfs(int c, int b, int t) {
        int i, prelen = -1;
        if ( 0 == c ) {
                // 剩余長度為 0，則開始拼裝下一根原始木棍，
                // 需擴(kuò)大嘗試的范圍。
                for ( i = 0; (i < cutnum) && (used[i]); ++i ) {
                }
                // 所有木棍都已經(jīng)被用于拼裝原始木棍，
                // 即嘗試成功。
                if ( i >= cutnum ) {
                        //printf("i >= cutnum, t = %d\n", t);
                        return 1;
                }
                used[ i ] = 1;
                //choice[ t ] = i;
                // 任一原始木棍中，必含有剩余木棍中最長的那根
                if ( dfs(orglen-cutlen[i], i+1, t+1) ) {
                        return 1;
                }
                used[ i ] = 0;
                return 0;
        }
        for ( i = b; i < cutnum; ++i ) {
                if (    (used[ i ]) ||          // 木棍沒用過
                        (c < cutlen[i]) ||      // 剩余長度能容納此木棍
                        (prelen == cutlen[i])   // 此長度的木棍已經(jīng)試過，不行，無需再試
                ) {
                        continue;
                }
                used[ i ] = 1;
                //choice[ t ] = i;

                // 下次嘗試從后面的木棍開始，前面的木棍無需考慮
                if ( dfs(c-cutlen[i], i+1, t+1) ) {
                        return 1;
                }

                prelen = cutlen[ i ];

                used[ i ] = 0;

                // 存在一木棍剛好可以符合剩余長度，則不再嘗試其它
                if ( c == cutlen[ i ] ) {
                        return 0;
                }
        }
        return 0;
}

int find(){
        // 原始木棍長度必為總長度的約數(shù)
        if ( 0 != totlen % orglen ) {
                return 0;
        }
        orgnum = totlen / orglen;
        memset(used, 0, sizeof(used));
        return dfs(0, 0, 0);
}

int main() {
        int i;
        while ( (1 == scanf("%d", &cutnum)) && (0 < cutnum) ) {
                totlen = 0;
                for ( i = 0; i < cutnum; ++i ) {
                        scanf("%d", cutlen+i);
                        totlen += cutlen[ i ];
                }
                // 將木棍從長到短排序，然后從長到短搜索之
                qsort(cutlen, cutnum, sizeof(cutlen[0]), cmp);
                // 原始木棍長度必大于等于最長木棍長度，
                // 小于等于木棍總長度，
                // 從短到長枚舉原始木棍長度。
                for ( orglen = cutlen[0]; (orglen < totlen) && (! find()); ++orglen ) {
                }
                printf("%d\n", orglen);
                //if ( orglen != totlen ) {
                //        for ( i = 0; i < cutnum; ++i ) {
                //                printf("--%d--", choice[ i ]);
                //        }
                //        printf("\n");
                //}
        }
        return 0;
}
*/


/**********************************************************
版本一：
EOJ  1981  TLE
POJ  1011  16MS  164K
HDOJ 1455  0MS   188K
UVA  307   TLE
*/
/*
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define  L  70

int cutnum;                 // 木棍的數(shù)量
int cutlen[ L ], totlen;    // 木棍的各自長度，及總長度

int cmp( const void *pa, const void *pb) {
        return (*((int*)pb)) - (*((int*)pa));
}

int orglen, orgnum; // 原始木棍的長度及其數(shù)量
int used[ L ];      // dfs 時標(biāo)記某木棍是否已經(jīng)被用于組裝原始木棍
//int choice[ L ];

        // 嘗試拼裝某原始木棍，
        // 此次嘗試之前，
        // 已經(jīng)使用了 t 根木棍，
        // 已經(jīng)拼裝出了原始木棍的部分長度，剩余 c 長度需要拼裝，
        // 此次嘗試，只需要從第 b 根木棍開始。
int dfs(int c, int b, int t) {
        int i, prelen = -1;
        if ( 0 == c ) {
                // 剩余長度為 0，則開始拼裝下一根原始木棍，
                // 需擴(kuò)大嘗試的范圍。
                for ( i = 0; (i < cutnum) && (used[i]); ++i ) {
                }
                // 所有木棍都已經(jīng)被用于拼裝原始木棍，
                // 即嘗試成功。
                if ( i >= cutnum ) {
                        //printf("i >= cutnum, t = %d\n", t);
                        return 1;
                }
                used[ i ] = 1;
                //choice[ t ] = i;
                // 任一原始木棍中，必含有剩余木棍中最長的那根
                if ( dfs(orglen-cutlen[i], i+1, t+1) ) {
                        return 1;
                }
                used[ i ] = 0;
                return 0;
        }
        for ( i = b; i < cutnum; ++i ) {
                if (    (used[ i ]) ||          // 木棍沒用過
                        (c < cutlen[i]) ||      // 剩余長度能容納此木棍
                        (prelen == cutlen[i])   // 此長度的木棍已經(jīng)試過，不行，無需再試
                ) {
                        continue;
                }
                used[ i ] = 1;
                //choice[ t ] = i;

                // 下次嘗試從后面的木棍開始，前面的木棍無需考慮
                if ( dfs(c-cutlen[i], i+1, t+1) ) {
                        return 1;
                }
                prelen = cutlen[ i ];

                used[ i ] = 0;
        }
        return 0;
}

int find(){
        // 原始木棍長度必為總長度的約數(shù)
        if ( 0 != totlen % orglen ) {
                return 0;
        }
        orgnum = totlen / orglen;
        memset(used, 0, sizeof(used));
        return dfs(0, 0, 0);
}

int main() {
        int i;
        while ( (1 == scanf("%d", &cutnum)) && (0 < cutnum) ) {
                totlen = 0;
                for ( i = 0; i < cutnum; ++i ) {
                        scanf("%d", cutlen+i);
                        totlen += cutlen[ i ];
                }
                // 將木棍從長到短排序，然后從長到短搜索之
                qsort(cutlen, cutnum, sizeof(cutlen[0]), cmp);
                // 原始木棍長度必大于等于最長木棍長度，
                // 小于等于木棍總長度，
                // 從短到長枚舉原始木棍長度。
                for ( orglen = cutlen[0]; (orglen < totlen) && (! find()); ++orglen ) {
                }
                printf("%d\n", orglen);
                //if ( orglen != totlen ) {
                //        for ( i = 0; i < cutnum; ++i ) {
                //                printf("--%d--", choice[ i ]);
                //        }
                //        printf("\n");
                //}
        }
        return 0;
}
*/

posted on 2012-04-21 10:47 coreBugZJ 閱讀(3203) 評論(0)  編輯 收藏 引用 所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <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>
            
99热精品在线观看|
一区二区三区欧美视频|
亚洲美女中文字幕|
亚洲欧美精品suv|
久久综合伊人77777|
国产精品国产a|
在线不卡视频|
亚洲综合另类|
欧美激情一二三区|
亚洲欧美日韩精品久久|
欧美搞黄网站|
狠狠色伊人亚洲综合成人|
在线综合+亚洲+欧美中文字幕|
久久精品国产久精国产一老狼|
亚洲国产视频一区|
午夜亚洲一区|
欧美日韩亚洲一区二区三区四区|
国产小视频国产精品|
一区二区精品国产|
久久一二三四|
亚洲视频中文字幕|
欧美黄色精品|
韩日在线一区|
午夜精品国产|
亚洲黄色免费|
久久久久久网址|
国产精品麻豆成人av电影艾秋|
91久久精品久久国产性色也91|
久久se精品一区精品二区|
亚洲免费大片|
欧美不卡福利|
亚洲成色777777在线观看影院|
午夜天堂精品久久久久|
亚洲精品一级|
美女国内精品自产拍在线播放|
国产日产欧产精品推荐色|
亚洲午夜精品久久久久久app|
欧美国产激情二区三区|
久久精品女人的天堂av|
国产日韩精品视频一区|
亚洲综合久久久久|
日韩视频欧美视频|
欧美精品久久久久久久|
亚洲人成7777|
欧美激情视频一区二区三区免费|
久久国产日本精品|
国产香蕉97碰碰久久人人|
亚洲欧美一级二级三级|
日韩一区二区福利|
欧美日韩在线观看一区二区|
91久久国产自产拍夜夜嗨|
嫩草国产精品入口|
久久久久久欧美|
一区在线播放视频|
久久这里只有精品视频首页|
欧美一区激情|
国产综合第一页|
久久久久久一区二区|
小黄鸭精品密入口导航|
国产亚洲成年网址在线观看|
欧美中在线观看|
香蕉精品999视频一区二区|
国产欧美亚洲一区|
久久久久.com|
久久久久久久久久久久久久一区
|
欧美第十八页|
最新精品在线|
91久久精品日日躁夜夜躁欧美
|
亚洲日本欧美在线|
亚洲国产欧美日韩另类综合|
欧美xxxx在线观看|
亚洲久久成人|
99国产欧美久久久精品|
欧美日韩综合一区|
亚洲欧美日韩一区二区在线|
亚洲伊人伊色伊影伊综合网|
国产乱码精品一区二区三区av|
欧美亚洲自偷自偷|
欧美一激情一区二区三区|
黑人一区二区|
亚洲国产精品第一区二区|
欧美人与禽猛交乱配|
亚洲夜间福利|
午夜精品理论片|
亚洲成人自拍视频|
亚洲欧洲日产国产综合网|
欧美三级在线播放|
久久国产欧美|
久久在线免费|
正在播放日韩|
午夜精品一区二区三区在线|
在线不卡亚洲|
亚洲美女毛片|
国产在线播精品第三|
欧美韩日一区|
国产精品久久久久久妇女6080|
久久国产精品久久久久久久久久|
久久久久高清|
在线一区亚洲|
久久精品二区亚洲w码|
亚洲精品欧美精品|
亚洲欧美国产视频|
亚洲国产精品毛片|
一区二区三区欧美视频|
国内成+人亚洲|
亚洲欧洲精品一区二区三区波多野1战4
|
久久av一区二区三区漫画|
久久一区二区三区av|
在线综合亚洲|
久久久精品国产一区二区三区|
亚洲美女91|
欧美在线综合|
99日韩精品|
久久国产福利|
中日韩午夜理伦电影免费|
久久精品99国产精品|
一区二区三区不卡视频在线观看|
午夜宅男欧美|
中文精品视频|
久久麻豆一区二区|
午夜精品久久久久久久99热浪潮|
久久久亚洲综合|
午夜精品www|
欧美精品日韩综合在线|
欧美一区二区大片|
欧美日韩a区|
美国十次成人|
国产欧美日韩综合一区在线观看|
欧美黄色成人网|
国产一区在线视频|
在线中文字幕一区|
亚洲欧洲在线免费|
久久九九精品99国产精品|
亚洲免费一级电影|
欧美精品国产精品|
老司机免费视频一区二区三区|
欧美午夜不卡影院在线观看完整版免费|
美女精品视频一区|
国产欧美日韩视频在线观看|
亚洲精品字幕|
亚洲三级电影在线观看|
欧美在线一区二区三区|
香蕉乱码成人久久天堂爱免费|
欧美黄色影院|
欧美激情免费在线|
黄色成人在线免费|
欧美一区二区大片|
午夜久久久久久|
欧美日韩在线视频一区|
最新成人av在线|
亚洲国产第一|
久久免费高清视频|
久久国产主播精品|
国产精品一卡二卡|
亚洲一卡二卡三卡四卡五卡|
一区二区三区免费网站|
欧美黄免费看|
91久久国产综合久久蜜月精品
|
亚洲区一区二区三区|
在线精品国产成人综合|
久久精品国产v日韩v亚洲|
久久激情视频久久|
国产伦精品一区二区三区免费迷|
亚洲视频1区2区|
亚洲欧美国产高清|
国产精品爱久久久久久久|
日韩视频第一页|
夜夜嗨av一区二区三区中文字幕
|
一本大道久久精品懂色aⅴ|
模特精品裸拍一区|
欧美成人激情视频免费观看|
136国产福利精品导航网址|
久久久久久久一区|
欧美成年人网站|
亚洲国产另类 国产精品国产免费|
久久全国免费视频|
农村妇女精品|
最新亚洲一区|
欧美精品一区二区三区视频|
亚洲日韩成人|
亚洲一区二区三区高清不卡|
欧美无乱码久久久免费午夜一区|
一本久久青青|
欧美一级理论片|
国产真实久久|
久久综合网络一区二区|
亚洲大片在线|
亚洲视频网站在线观看|
国产精品美女久久久久久免费|
亚洲一级高清|
久久免费黄色|
91久久综合|
欧美日韩天堂|
亚洲自拍偷拍一区|
久久香蕉国产线看观看网|
亚洲高清毛片|
欧美日韩综合视频|
午夜视黄欧洲亚洲|
欧美国产日韩在线观看|
av成人动漫|