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> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define dbg(x) cerr<<#x<<" = "<<x<<endl 8 #define dddbg(x,y,z) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl 9 using namespace std; 10 typedef long long ll; 11 typedef pair<int,int> pii; 12 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 13 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 14 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 15 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 16 template<typename T>inline T read(T&x){ 17 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 18 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 19 } 20 inline char cmp(int a,int b){return a>b;} 21 const int N=67; 22 int a[N],vis[N],suf[N],n,lmax,lsum,len; 23 int dfs(int rest,int pre,int sum){//dddbg(rest,pre,len); 24 if(!rest){ 25 if(!sum||sum==len)return 1;//后面那个稍微节省少许时间 26 else{ 27 rest=len;int flag=0; 28 for(register int i=1;i<=n;++i)if(!vis[i]){pre=i;break;} 29 vis[pre]=1,flag=dfs(rest-a[pre],pre,sum-a[pre]),vis[pre]=0;//★较强剪枝 30 return flag; 31 } 32 } 33 int flag=0; 34 for(register int i=pre+1;i<=n;++i)//★强剪枝 35 if(flag)break; 36 else if(!vis[i]&&a[i]<=rest){ 37 vis[i]=1,flag|=dfs(rest-a[i],i,sum-a[i]),vis[i]=0; 38 if(!flag){ 39 if(rest==a[i])return 0;//★强剪枝 40 while(a[i]==a[i+1])++i;//★强剪枝 41 } 42 }//二分不写了 43 return flag; 44 } 45 46 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout); 47 read(n);int tmp=0,x; 48 for(register int i=1;i<=n;++i)read(x),x<=50?(lsum+=x,MAX(lmax,a[++tmp]=x)):0; 49 n=tmp;sort(a+1,a+n+1,cmp);//★强剪枝 50 for(len=lmax;len<=(lsum)>>1;++len)//没用的剪枝 51 if(lsum%len==0&&dfs(0,0,lsum))break; 52 printf("%d ",len>(lsum>>1)?lsum:len); 53 return 0; 54 }
poj版本
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define dbg(x) cerr<<#x<<" = "<<x<<endl 8 #define dddbg(x,y,z) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl 9 using namespace std; 10 typedef long long ll; 11 typedef pair<int,int> pii; 12 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 13 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 14 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 15 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 16 template<typename T>inline T read(T&x){ 17 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 18 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 19 } 20 inline char cmp(int a,int b){return a>b;} 21 const int N=67; 22 int a[N],vis[N],suf[N],n,lmax,lsum,len,tot; 23 int dfs(int rest,int pre,int sum){//dddbg(rest,pre,len); 24 if(!rest){ 25 if(!sum||sum==len)return 1;//后面那个稍微节省少许时间 26 else{ 27 rest=len;int flag=0; 28 for(register int i=1;i<=n;++i)if(!vis[i]){pre=i;break;} 29 vis[pre]=1,flag=dfs(rest-a[pre],pre,sum-a[pre]),vis[pre]=0;//★较强剪枝 30 return flag; 31 } 32 } 33 int flag=0; 34 for(register int i=pre+1;i<=n;++i)//★强剪枝 35 if(flag)break; 36 else if(!vis[i]&&a[i]<=rest){ 37 vis[i]=1,flag|=dfs(rest-a[i],i,sum-a[i]),vis[i]=0; 38 if(!flag){ 39 if(rest==a[i])return 0;//★强剪枝 40 while(a[i]==a[i+1])++i;//★强剪枝 41 } 42 }//二分不写了 43 return flag; 44 } 45 46 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout); 47 while(read(n)){ 48 lmax=lsum=0; 49 for(register int i=1;i<=n;++i)MAX(lmax,read(a[i])),lsum+=a[i]; 50 sort(a+1,a+n+1,cmp);tot=0;//★强剪枝 51 for(len=lmax;len<=(lsum)>>1;++len,tot=0)//没用的剪枝 52 if(lsum%len==0&&dfs(0,0,lsum))break; 53 printf("%d ",len>(lsum>>1)?lsum:len); 54 } 55 return 0; 56 }