POJ 1011 - Sticks DFS+剪枝

POJ 1011 - Sticks
题意：
    一把等长的木段被随机砍成 n 条小木条
    已知他们各自的长度，问原来这些木段可能的最小长度是多少

分析：
    1. 该长度必能被总长整除
    2. 从大到小枚举，因为小长度更灵活， 可拼接可不拼接
    3. 因为每一跟木条都要用到， 故若轮到其中一根原始木段选它的第一根木条时，若第一根木条若不满足，则显然第一根木条在接下来任何一根原始木段都不会满足，故无解
    4. 由于所有棒子已排序，在DFS时，若某根棒子未被选，则跳过其后面所有与它等长的棒子

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int n, sum, ans, len, Max;

 int a[],vis[];

 bool dfs(int num,int x,int j)

 {

     if(x == )

     {

         num--;

         if(num == ) return ;

         int i = n;

         while(vis[i]) i--;

         vis[i] = ;

         if(dfs(num, len - a[i], i-) ) return ;

         vis[i] = ;

     }

     else

     {

         for (int i = j; i > ; i--)

         {

             if (vis[i]) continue;

             if (!vis[i+] && a[i+] == a[i]) continue;

             if (x < a[i]) continue;

             vis[i] = ;

             if(dfs(num, x - a[i], i-)) return ;

             vis[i] = ;

         }

     }

     return ;

 }

 int main()

 {

     while(~scanf("%d",&n) && n)

     {

         sum = , Max = ;

         for (int i = ; i <= n; i++){

             scanf("%d", &a[i]);

             sum += a[i];

             Max = max(a[i], Max);

         }

         sort(a+,a++n);

         ans = sum;

         for (int i = Max; i < sum ; i++)

         {

             if (sum % i) continue;

             len = i;

             memset(vis,,sizeof(vis));

             if(dfs(sum/i, len, n))

             {

                 ans = i;

                 break;

             }

         }

         printf("%d\n", ans);

     }

 }