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

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			ACM搜索題經典 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


            ----分析：

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

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


            ----幾組比較強的測試數據：

            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

            增加搜索次數限制。

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

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

            #define  L  70

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

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

            int orglen, orgnum; // 原始木棍的長度及其數量
            int used[ L ];      // dfs 時標記某木棍是否已經被用于組裝原始木棍
            //int choice[ L ];

            // 若搜索次數超過此值，則認為不可能成功
            #define  LIM  100000
            int lim;
                                // 嘗試拼裝某原始木棍，
                                // 此次嘗試之前，
                                // 已經使用了 t 根木棍，
                                // 已經拼裝出了原始木棍的部分長度，剩余 c 長度需要拼裝，
                                // 此次嘗試，只需要從第 b 根木棍開始。
            int dfs(int c, int b, int t) {
                                int i, prelen = -1;
                                if ( --lim <= 0 ) {
                                        return 0;
                    }
                                if ( 0 == c ) {
                                        // 剩余長度為 0，則開始拼裝下一根原始木棍，
                                        // 需擴大嘗試的范圍。
                            for ( i = 0; (i < cutnum) && (used[i]); ++i ) {
                            }
                                        // 所有木棍都已經被用于拼裝原始木棍，
                                        // 即嘗試成功。
                            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])   // 此長度的木棍已經試過，不行，無需再試
                            ) {
                                                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(){
                                // 原始木棍長度必為總長度的約數
                    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;                 // 木棍的數量
            int cutlen[ L ], totlen;    // 木棍的各自長度，及總長度

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

            int orglen, orgnum; // 原始木棍的長度及其數量
            int used[ L ];      // dfs 時標記某木棍是否已經被用于組裝原始木棍
            //int choice[ L ];

                    // 嘗試拼裝某原始木棍，
                    // 此次嘗試之前，
                    // 已經使用了 t 根木棍，
                    // 已經拼裝出了原始木棍的部分長度，剩余 c 長度需要拼裝，
                    // 此次嘗試，只需要從第 b 根木棍開始。
            int dfs(int c, int b, int t) {
                    int i, prelen = -1;
                    if ( 0 == c ) {
                            // 剩余長度為 0，則開始拼裝下一根原始木棍，
                            // 需擴大嘗試的范圍。
                            for ( i = 0; (i < cutnum) && (used[i]); ++i ) {
                            }
                            // 所有木棍都已經被用于拼裝原始木棍，
                            // 即嘗試成功。
                            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])   // 此長度的木棍已經試過，不行，無需再試
                            ) {
                                    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(){
                    // 原始木棍長度必為總長度的約數
                    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;                 // 木棍的數量
            int cutlen[ L ], totlen;    // 木棍的各自長度，及總長度

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

            int orglen, orgnum; // 原始木棍的長度及其數量
            int used[ L ];      // dfs 時標記某木棍是否已經被用于組裝原始木棍
            //int choice[ L ];

                    // 嘗試拼裝某原始木棍，
                    // 此次嘗試之前，
                    // 已經使用了 t 根木棍，
                    // 已經拼裝出了原始木棍的部分長度，剩余 c 長度需要拼裝，
                    // 此次嘗試，只需要從第 b 根木棍開始。
            int dfs(int c, int b, int t) {
                    int i, prelen = -1;
                    if ( 0 == c ) {
                            // 剩余長度為 0，則開始拼裝下一根原始木棍，
                            // 需擴大嘗試的范圍。
                            for ( i = 0; (i < cutnum) && (used[i]); ++i ) {
                            }
                            // 所有木棍都已經被用于拼裝原始木棍，
                            // 即嘗試成功。
                            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])   // 此長度的木棍已經試過，不行，無需再試
                            ) {
                                    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(){
                    // 原始木棍長度必為總長度的約數
                    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 閱讀(3182) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



精品久久久噜噜噜久久久|
国产99久久九九精品无码|
怡红院日本一道日本久久
|
婷婷综合久久中文字幕|
AAA级久久久精品无码区|
99久久国产综合精品网成人影院|
久久精品亚洲乱码伦伦中文
|
国内精品久久久久久久影视麻豆|
欧美久久一级内射wwwwww.|
亚洲av成人无码久久精品|
狠狠色伊人久久精品综合网
|
国产成人精品综合久久久|
72种姿势欧美久久久久大黄蕉|
欧美粉嫩小泬久久久久久久|
久久精品嫩草影院|
欧美丰满熟妇BBB久久久|
久久九九免费高清视频|
久久香蕉国产线看观看99|
婷婷久久久亚洲欧洲日产国码AV|
久久高清一级毛片|
久久精品国产精品青草|
久久人妻少妇嫩草AV无码专区|
久久婷婷五月综合色99啪ak|
欧美综合天天夜夜久久|
国产91色综合久久免费分享|
99精品久久精品一区二区|
一本久久a久久精品综合香蕉
|
日本WV一本一道久久香蕉|
久久久WWW成人免费毛片|
青青草国产成人久久91网|
久久天堂电影网|
精品久久久久久无码专区不卡|
亚洲国产成人精品91久久久|
久久婷婷久久一区二区三区|
国产一区二区三区久久精品|
久久精品亚洲中文字幕无码麻豆|
av色综合久久天堂av色综合在|
伊人久久国产免费观看视频|
久久久久久国产精品美女|
久久人人爽人人爽人人片AV麻烦|
久久久国产视频|