POJ 1011 Sticks【深搜+剪枝】

向右看齐 2022-05-25 06:46 178阅读 0赞

## Sticks ##

Time Limit: 1000MS Memory Limit: 10000K  
Total Submissions: 152276 Accepted: 36300

#### Description ####

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 and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

#### Input ####

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.

#### Output ####

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

#### Sample Input ####

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

#### Sample Output ####

6  
5

#### 题意概括： ####

有n根木棒，将其拼成若干根长度相同的木棍，求拼成的木棍的最短长度。

#### 解题分析： ####

用深搜，把所有木棍去拼成几个长度相同的木棍，简单想一下直接深搜的话肯定会超时，需要剪枝。  
1、木棍长度最小等于最长木棍的长度，最长是拼成 两根，也就是每根的长度为ans/2（最后木棍数为两根及两根以上），还有就是所有木棍拼成一根。  
2、最后拼成的木棍长度L一定能被所有木棍的总长度ans整除。  
3、可以将所有木棍降序排一个序，先搜长的，因为一个长度为m的木棍肯定比几个长度加起来等于m的木棍好搜索，同时短的也比较容易跟其他的组合。  
4、当以一根木棍为第一根时若它没有拼成的话那后边的也一定拼不成，因为所有的木棍都要用上，所以当前的L可以结束搜索。  
5、当以一根木棍为拼成的一根木棍的最后一根后，后边的木棍若没有拼成，则以这根木棍不能作为最后一根，需从新搜索，但不一定当前长度L不能拼成。  
6、当一个长度被搜过且没有搜成的不用再搜。

#### AC代码： ####

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    #define N 100
    
    int n, coun, sum;
    int vis[N], e[N];
    
    bool cmp(int a, int b)
    {
        return a > b;
    }
    
    int dfs(int L, int sum, int t)
    {
    
        if(sum == L && t == n) return 1;
        if(sum == L) sum = 0;
        for(int i = 0; i < n; i++){
            if(i > 0 && !vis[i-1] && e[i] == e[i-1]) continue;//第六条剪枝
            if(vis[i] || sum+e[i] > L) continue;
            vis[i] = 1;
            if(dfs(L, sum+e[i], t+1)) return 1;
            else{
                vis[i] = 0;
                if(!sum || sum == L) return 0;//第四第五条的剪枝
            }
        }
        return 0;
    }
    
    int main()
    {
        int i, j, ans;
        while(scanf("%d", &n), n){
            for(i = ans = 0; i < n; i++){
                scanf("%d", &e[i]);
                ans += e[i];
            }
            sort(e, e+n, cmp);//第三条
            for(i = e[0]; i <= ans/2; i++){
       //第一条剪枝
                if(ans%i != 0) continue;//第二条剪枝
                memset(vis, 0, sizeof(vis));
                if(dfs(i, 0, 0)){
                    printf("%d\n", i);
                    break;
                }
            }
            if(i > ans/2) printf("%d\n", ans);
        }
        return 0;
    }