https://vjudge.net/problem/POJ-1011
此题很重要。★★★
很欢(e)乐(xin)的一道搜索剪枝题。。poj数据还是太水了，我后来想不出来剪枝方法了，就加了句掐了时间语句交上去骗了一个AC。。洛谷上加强数据掉了4个点。
由题意（翻译） ，要确定一个长度让所有短木棍拼的出来。由于数据看起来很小N只有64，所以要搜索。但是怎么搜还是关键。由于枚举长度不满足答案单调性，所以不好二分，只能从小到大枚举，找到就输出。每次check的dfs就是看可不可以选出恰好拼出一根长度len的，可以则继续拼下一根，直到恰好拼完就返回1。
下面讲剪枝即其他常数优化，没想到的加了下划线，是翻题解的。
剪枝一：枚举长度从最长木棍长度开始，这个不用说了吧。。然后一个几乎没用的优化，枚举长度到maxlen/2还不行就只能输出maxlen了。
剪枝二：避免完全无效的搜索，每次枚举的长棍如果不能整除累计总长的话，肯定拼不上来的呢。
剪枝三：木棍len要从大到小去拼。这个没法证，就是一种感觉（生活经验）：先定下大的，再用碎的去凑上可能会更高效。强剪枝。
剪枝四：要考虑什么情况会造成搜索的时候重复搜索。分析可知，我现在选了这一根棒拼上去，下一根就按顺序找后面的就行了，否则我可能下次选了后面那根，再选前面的这根，就属于重复的。即为代码中的pre。
剪枝五：考虑拼完一根木棒后，不要再像code中的line34那样去找没用过的填上去。试想，我在剩下的里面拼不了了。我已经知道现在肯定不行，就果断返回。否则还会再搜当下其他棒。具体对应line26开始的，也就是我随便找一个开始填，能就能，不能就不能，反正他迟早被用。中强剪枝。
剪枝六：（pj组都会的常识）用flag标记以提前退出。
剪枝七：最有效的剪枝之一，比较难想，可能我太菜了。继剪枝五，如果我现在这根填完恰好拼凑成了一根长棍，下次开始重新拼不行的话，那放弃之后的枚举，直接返回失败。用反证法瞎想一下：已知当前用的长棒恰填好一长棍，剩下的拼不了了，假设我存在一种用之后的更短木棍拼好当前长棍，剩下的能拼完的方案，那我完全可以把短的木棒看成拼出之前那一根木棒的效果，我完全可以交换一下两者位置，则同样可行，与已知矛盾，得证。举个例子，8 5 3 1 2，假若5恰好拼出来了，后面不行。我可以换用3和2达到同样效果，但用反证法发现也不行。最强剪枝
剪枝八：长度相同的木棒，当我用其中一个填入时不行，另外的就不试了。很好想，实测效果也很好。强剪枝。
剪枝九：这个没写，觉得没必要，就是二分找第一个比rest小的木棒。
这题剪枝很多，而且在luogu强数据下，少一个基本都要TLE。希望记住这些思路。
坑死我了，写了几个小时。
WA记录：？不存在，只有TLE。
luogu版本
1 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define dddbg(x,y,z) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
inline char cmp(int a,int b){return a>b;}
const int N=;
int a[N],vis[N],suf[N],n,lmax,lsum,len;
int dfs(int rest,int pre,int sum){//dddbg(rest,pre,len);
if(!rest){
if(!sum||sum==len)return ;//后面那个稍微节省少许时间
else{
rest=len;int flag=;
for(register int i=;i<=n;++i)if(!vis[i]){pre=i;break;}
vis[pre]=,flag=dfs(rest-a[pre],pre,sum-a[pre]),vis[pre]=;//★较强剪枝
return flag;
}
}
int flag=;
for(register int i=pre+;i<=n;++i)//★强剪枝
if(flag)break;
else if(!vis[i]&&a[i]<=rest){
vis[i]=,flag|=dfs(rest-a[i],i,sum-a[i]),vis[i]=;
if(!flag){
if(rest==a[i])return ;//★强剪枝
while(a[i]==a[i+])++i;//★强剪枝
}
}//二分不写了
return flag;
} int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
read(n);int tmp=,x;
for(register int i=;i<=n;++i)read(x),x<=?(lsum+=x,MAX(lmax,a[++tmp]=x)):;
n=tmp;sort(a+,a+n+,cmp);//★强剪枝
for(len=lmax;len<=(lsum)>>;++len)//没用的剪枝
if(lsum%len==&&dfs(,,lsum))break;
printf("%d\n",len>(lsum>>)?lsum:len);
return ;
}
poj版本
1 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define dddbg(x,y,z) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
inline char cmp(int a,int b){return a>b;}
const int N=;
int a[N],vis[N],suf[N],n,lmax,lsum,len,tot;
int dfs(int rest,int pre,int sum){//dddbg(rest,pre,len);
if(!rest){
if(!sum||sum==len)return ;//后面那个稍微节省少许时间
else{
rest=len;int flag=;
for(register int i=;i<=n;++i)if(!vis[i]){pre=i;break;}
vis[pre]=,flag=dfs(rest-a[pre],pre,sum-a[pre]),vis[pre]=;//★较强剪枝
return flag;
}
}
int flag=;
for(register int i=pre+;i<=n;++i)//★强剪枝
if(flag)break;
else if(!vis[i]&&a[i]<=rest){
vis[i]=,flag|=dfs(rest-a[i],i,sum-a[i]),vis[i]=;
if(!flag){
if(rest==a[i])return ;//★强剪枝
while(a[i]==a[i+])++i;//★强剪枝
}
}//二分不写了
return flag;
} int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
while(read(n)){
lmax=lsum=;
for(register int i=;i<=n;++i)MAX(lmax,read(a[i])),lsum+=a[i];
sort(a+,a+n+,cmp);tot=;//★强剪枝
for(len=lmax;len<=(lsum)>>;++len,tot=)//没用的剪枝
if(lsum%len==&&dfs(,,lsum))break;
printf("%d\n",len>(lsum>>)?lsum:len);
}
return ;
}