• <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搜索題經(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


            ----分析：

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

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


            ----幾組比較強(qiáng)的測(cè)試數(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;    // 木棍的各自長(zhǎng)度，及總長(zhǎng)度

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

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

            // 若搜索次數(shù)超過此值，則認(rèn)為不可能成功
            #define  LIM  100000
            int lim;
                                // 嘗試拼裝某原始木棍，
                                // 此次嘗試之前，
                                // 已經(jīng)使用了 t 根木棍，
                                // 已經(jīng)拼裝出了原始木棍的部分長(zhǎng)度，剩余 c 長(zhǎng)度需要拼裝，
                                // 此次嘗試，只需要從第 b 根木棍開始。
            int dfs(int c, int b, int t) {
                                int i, prelen = -1;
                                if ( --lim <= 0 ) {
                                        return 0;
                    }
                                if ( 0 == c ) {
                                        // 剩余長(zhǎng)度為 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;
                                        // 任一原始木棍中，必含有剩余木棍中最長(zhǎng)的那根
                            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]) ||      // 剩余長(zhǎng)度能容納此木棍
                                    (prelen == cutlen[i])   // 此長(zhǎng)度的木棍已經(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;

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

            int find(){
                                // 原始木棍長(zhǎng)度必為總長(zhǎng)度的約數(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 ];
                            }
                                        // 將木棍從長(zhǎng)到短排序，然后從長(zhǎng)到短搜索之
                            qsort(cutlen, cutnum, sizeof(cutlen[0]), cmp);

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

                                        // 原始木棍長(zhǎng)度必大于等于最長(zhǎng)木棍長(zhǎng)度，
                                        // 小于等于木棍總長(zhǎng)度，
                                        // 從短到長(zhǎng)枚舉原始木棍長(zhǎng)度。
                            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;    // 木棍的各自長(zhǎng)度，及總長(zhǎng)度

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

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

                    // 嘗試拼裝某原始木棍，
                    // 此次嘗試之前，
                    // 已經(jīng)使用了 t 根木棍，
                    // 已經(jīng)拼裝出了原始木棍的部分長(zhǎng)度，剩余 c 長(zhǎng)度需要拼裝，
                    // 此次嘗試，只需要從第 b 根木棍開始。
            int dfs(int c, int b, int t) {
                    int i, prelen = -1;
                    if ( 0 == c ) {
                            // 剩余長(zhǎng)度為 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;
                            // 任一原始木棍中，必含有剩余木棍中最長(zhǎng)的那根
                            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]) ||      // 剩余長(zhǎng)度能容納此木棍
                                    (prelen == cutlen[i])   // 此長(zhǎng)度的木棍已經(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;

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

            int find(){
                    // 原始木棍長(zhǎng)度必為總長(zhǎng)度的約數(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 ];
                            }
                            // 將木棍從長(zhǎng)到短排序，然后從長(zhǎng)到短搜索之
                            qsort(cutlen, cutnum, sizeof(cutlen[0]), cmp);
                            // 原始木棍長(zhǎng)度必大于等于最長(zhǎng)木棍長(zhǎng)度，
                            // 小于等于木棍總長(zhǎng)度，
                            // 從短到長(zhǎng)枚舉原始木棍長(zhǎng)度。
                            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;    // 木棍的各自長(zhǎng)度，及總長(zhǎng)度

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

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

                    // 嘗試拼裝某原始木棍，
                    // 此次嘗試之前，
                    // 已經(jīng)使用了 t 根木棍，
                    // 已經(jīng)拼裝出了原始木棍的部分長(zhǎng)度，剩余 c 長(zhǎng)度需要拼裝，
                    // 此次嘗試，只需要從第 b 根木棍開始。
            int dfs(int c, int b, int t) {
                    int i, prelen = -1;
                    if ( 0 == c ) {
                            // 剩余長(zhǎng)度為 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;
                            // 任一原始木棍中，必含有剩余木棍中最長(zhǎng)的那根
                            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]) ||      // 剩余長(zhǎng)度能容納此木棍
                                    (prelen == cutlen[i])   // 此長(zhǎng)度的木棍已經(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(){
                    // 原始木棍長(zhǎng)度必為總長(zhǎng)度的約數(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 ];
                            }
                            // 將木棍從長(zhǎng)到短排序，然后從長(zhǎng)到短搜索之
                            qsort(cutlen, cutnum, sizeof(cutlen[0]), cmp);
                            // 原始木棍長(zhǎng)度必大于等于最長(zhǎng)木棍長(zhǎng)度，
                            // 小于等于木棍總長(zhǎng)度，
                            // 從短到長(zhǎng)枚舉原始木棍長(zhǎng)度。
                            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 閱讀(3185) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久久久亚洲AV无码专区体验|
久久久久久久人妻无码中文字幕爆|
狠狠精品久久久无码中文字幕|
久久av高潮av无码av喷吹|
天堂无码久久综合东京热|
国产亚洲精久久久久久无码77777|
97热久久免费频精品99|
一级做a爰片久久毛片免费陪|
久久精品99久久香蕉国产色戒|
精品久久人人爽天天玩人人妻|
国产精品一区二区久久精品涩爱|
精品久久一区二区|
久久人人爽人人人人爽AV|
国产成人精品久久一区二区三区av
|
四虎国产精品免费久久5151
|
精品久久久久久无码专区
|
亚洲AV日韩AV永久无码久久|
欧美精品一区二区精品久久|
亚洲精品乱码久久久久久自慰|
久久精品视屏|
88久久精品无码一区二区毛片|
无码人妻久久久一区二区三区|
超级97碰碰碰碰久久久久最新|
久久精品国产亚洲av瑜伽|
久久夜色精品国产亚洲|
蜜臀久久99精品久久久久久小说|
精品国产乱码久久久久软件|
精品久久人人爽天天玩人人妻|
丰满少妇人妻久久久久久4|
久久r热这里有精品视频|
久久er99热精品一区二区|
中文字幕久久精品无码|
久久久久国产精品人妻|
久久亚洲精品国产精品婷婷|
久久久99精品成人片中文字幕
|
久久精品视频网|
国产精品久久久久久久久免费|
国产精品99久久99久久久|
99久久精品午夜一区二区|
老司机国内精品久久久久|
久久精品九九亚洲精品天堂|