【转自】为你而执着
思路是按分段数从给定值开始依次减小搜索。
本题中所用到的剪枝技巧：
剪枝1：分段数res肯定能被总长度sum整除
剪枝2：每段的长度不可能大于初始分段的最大值
剪枝3：将输入的数据从大到小排序，因为一支长度为L的完整木棍肯定比几支短木棍拼成的同样长度的用处小（短小的用途更灵活一点）
剪枝4 ：找到结果之后在能返回的地方马上返回递归的上一层
剪枝5：相同长度的木棍不要搜索多次，用当前的这支搜下去得不出结果,那么用下一支同样长度的还是得不到结果
剪枝6：相当关键的剪枝，就是栽在这个剪枝上面两个多小时。判断当前长度是不是大于每段应该的长度，如果大于则没必要往下递归
剪枝7：不用说了，前面的肯定都用过了，所以从level+1开始
剪枝8： if(all-times+1
#include
#include
using namespace std;
int all,find1,res,times,used[65],stick[65];
int maxlen,lenth,sum;
void dfs(int no, int curlen, int level);
void fit(int no)
{
int i;
if(find1==1 || no>res){//find1==1剪枝4
find1 = 1;
return ;
}for(i=0; i) break;
}
used = 1;
times++;
dfs(no, stick, i);
times--;
used = 0;
}//剪枝：以当前最大值开始搜索一遍，无结果，返回
void dfs(int no, int curlen, int level)
{
if(curlen == lenth){
fit(no+1);
return ;
}
if(find1==1)//剪枝4
return ;
int i,j;
for(i=level+1; i && curlen+stick<=lenth){//剪枝6
//就是忘了这个最基本的 curlen+stick<=lenth剪枝导致TLE了一晚上
if(all-times+1 = 1;
times++;
dfs(no, curlen+stick, i);
times--;
used = 0;
j=i;
if(find1==1)//剪枝4，去掉多出15ms
return ;
while(i)//剪枝5,去掉则TLE
i++;
if(i==all)return ;
if(i!=j)i--;
}
}
}
void work()
{
if(sum%res!=0)//剪枝1
return ;
lenth = sum / res;
if(maxlen > lenth)//剪枝2
return ;
times = 0;
fit(1);
}
int main()
{
int i;
while(1){
sum = 0;
maxlen = 0;
scanf("%d", &all);
if(all==0)
break;
for(i=0; i);
if(maxlen)
maxlen = stick;
sum += stick;
}
sort(stick, stick+all, greater());//剪枝3
memset(used, 0, sizeof(used));
times = 0;
for(res=all; res>0; res--){
find1 = 0;
work();
if(find1==1)
break;
}
printf("%d\n",sum / res);
}
return 0;
}
