POJ1011-Sticks

Sticks
Time Limit 1000MS Memory Limit 10000K
Total Submissions 117588 Accepted 27100
Description
翻译：
问题描述：乔治拿来一组等长的木棒，将它们随机地裁断，使得每一节木棒的长度都不超过50个长度单位。然后他又想把这些木棒恢复到为裁截前的状态
，但忘记了木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棒的长度都用大于零的整数表示
输入：
由多个案例组成，每个案例包括两行。第一行是一个不超过64的整数，表示裁截之后共有多少节木棒。第二行是经过裁截后，所得到的各节木棒的长度。
在最后一个案例之后，是零。
输出：
为每个案例，分别输出木棒的可能最小长度。每个案例占一行。
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5

解题思路
初始状态：有N节木棒。最终状态：这N节木棒恰好被拼接成若干根等长的木棒。
从初始状态到最终状态最多有多少条不同的“路径”(指原始单个木棒可能的长度）？
Sum/maxParts。其中Sum是全部N节木棒的长度之和，maxParts是最
长一节木棒的长度
。
每条“路径”对应一个木棒的长度。从木棒长度最小的那条可能“路径”开始，如果成功地的找到了这条“路径”，就解决了问题DFS深搜
构造一条木棒长度为L的“路径”：拼接木棒
在未被拼接的木棒中，找出一节最长的，开始拼接

从未拼接的木棒中，选择一个长度合适的木棒，使得拼接后的木棒长度≤L1.找到了：
在前面的拼接过程中曾试图用过相同长度的一节其他木棒，但发现这样拼接不成功，继续寻找能够进行拼接的木棒

把找到的那节木棒拼接上去。

   继续进行拼接   继续拼接成功，找到了“路径”

   继续拼接不成功，把刚拼接的那节木棒拿下来，继续找下一个合适的未   拼接木帮

2.没有找到：拼接失败

bool  Dfs(int nUnusedSticks, int nLeft ) ;

表示: 当前有nUnusedSticks根未用木棒，而且当前正在拼的那根棍子比假定的棍子长度短了nLeft, 那么在这种情况下能全部否拼成功。

AC代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int len[100],flag[100],L;
int n,sum;
int cmp(int a,int b)
{
    if(a!=b) return a>b;
}
int DFS(int num,int nLeft)
// nLeft表示当前正在拼的棍子和L比还缺的长度
{
   int i;
   if(num==0&&nLeft==0)
   return 1;
   if(nLeft==0)//一根刚刚拼完
   nLeft=L;//开始拼新的一根
   for(i=0;i<n;i++)
   {
      if(!flag[i]&&len[i]<=nLeft)//如果此棒没有用过而且小于等于和L比还缺的长度
      {
         if(i>0)
         {
            if(flag[i-1]==0&&len[i]==len[i-1])
            continue;//剪枝1
         }
         flag[i]=1;
         if(DFS(num-1,nLeft-len[i]))
         return 1;
         else
         {
             flag[i] = 0;//说明不能用i作为
						//第１条，
						//那么要拆以前的
						//棍子，i还可能用
						//在以前的棍子里，
					     //因此要　flag[i]=0;
			 if(len[i]==nLeft||nLeft==L)
		     return 0;//剪枝2

         }
      }
   }
   return 0;
}
int main()
{
    int i;
    while(scanf("%d",&n)&&n)
    {
       sum=0;
       memset(len,0,sizeof(len));
       for(i=0;i<n;i++)
       {
          scanf("%d",&len[i]);
          sum+=len[i];
       }

       sort(len,len+n,cmp);

       for(L=len[0];L<=sum/2;L++)//从最长的那一根棒开始累加计算
       {
          if(sum%L)//木棒至少要有两截
          continue;
          memset(flag,0,sizeof(flag));//记录木棒是否被用过
          if(DFS(n,L))
          {
             printf("%d\n",L);
             break;
          }
       }
       if(L>sum/2)
       printf("%d\n",sum);//只有一根木棒被剪成几分
    }
    return 0;
}