传说中的poj必做50题之一……
这是个传说中的搜索，
一开始以为，
只要棒子加起来等于假设的原始长度，
那么这几根选择的棒子就不用管了，
结果卡在第一个样例……
看了一下，发现，
代码把1,2,1,2合成一个棒子，
这样其他就凑不成3根长度为6的棒子了，
写了半天，发现思路错了，
这个问题不知道如何解决。
参考了以下地址的结题报告：
http://blog.csdn.net/lyy289065406/article/details/6647960
找到了一个解决办法，
就是当合成了一个新的棒子的时候，
就重新从第一个棒子开始枚举，
用没有用过的棒子，开始合成新的棒子。
写好代码之后，各种TLE……
于是又参考了上面那个解题报告，
找了个剪枝的办法，
就是如果碰到用某个棒子为第一个棒子合成新棒子
的时候，无法得到我想要的那种棒子，
就直接退栈并返回一个0表示这样不行，
写好之后，结果还是TLE，
于是继续剪了个枝
就是一开始给棒子递增排个序，
然后如果在合成棒子的中途发现
合成失败，用这根棒子得不到想要的那种棒子，
就把这个棒子标记一下，
如果在这次合成中再次碰到一样长度的棒子，
就直接舍弃。
又写好了……还是TLE。。。
我就不明白了……
再TLE，我真的没办法了。
又参考了结题报告，
发现给棒子递减排序就可以，
想了一下为毛，
是这样的，因为优先加入长度较长的棒子，
更容易在比较少的次数里合成想要的那种棒子。
我的代码如下，欢迎讨论：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int stick[74],num_stk,sum_len;
bool used[74];
bool cmp(int a,int b)
{
return a>b;
}
void init()
{
int i;
sum_len=0;
for(i=0;i<num_stk;i++)
{
scanf("%d",&stick[i]);
sum_len+=stick[i];
}
}
bool dfs(int s,int nlen,int nnum,int olen)
{
int i,x=-1;
if(nnum==num_stk)
return 1;
for(i=s;i<num_stk;i++)
{
if(used[i]||stick[i]==x||nlen+stick[i]>olen)
continue;
used[i]=1;
if(nlen+stick[i]<olen)
{
if(dfs(i+1,nlen+stick[i],nnum+1,olen))
return 1;
}
else
{
if(dfs(0,0,nnum+1,olen))
return 1;
}
x=stick[i];
used[i]=0;
if(nlen==0)
return 0;
}
return 0;
}
void work()
{
int i;
memset(used,0,sizeof(used));
sort(stick,stick+num_stk,cmp);
for(i=stick[0];i+i<=sum_len;i++)
{
if(sum_len%i==0&&dfs(0,0,0,i))
{
printf("%d\n",i);
return;
}
}
printf("%d\n",sum_len);
}
int main()
{
while(scanf("%d",&num_stk)&&num_stk!=0)
{
init();
work();
}
}