洛谷P1120 小木棍 ［数据加强版］
https://www.luogu.org/problemnew/show/P1120
搜索函数的表示:search(int num,int rest)表示当前还剩下num根完整木棒和一根长度为rest的木棒待拼凑。
在非常多次复杂的递归中，一些看似很细节，对效率影响微乎其微的剪枝有可能对效率影响较大，不同的细节剪枝可能会在有不同特点的非随机数据中大展身手。最好就是把各种能想到的剪枝全都写出来，因为你不知道它究竟有没有用，写出来至少不会变慢。
1：对原木棍的长度的枚举范围最小是max{a(i)},即切后最长木棍的长度，最大是sum{a(i)}，即所有木棍的长度之和，并且设原木棍长度为len，则sum%len==0
2：切后木棍长度可能较分散，比如10，20，30，40，50，这样的话设置一个链表，处理50->40...->10,而不用50->49->48...
3：按从大到小的顺序枚举，因为小木棍比较灵活组合多样，先大后小有利于在解答树中更靠根结点的位置发现非法，不能继续搜索，从而剪掉一大棵子树，即加快了回溯，先小后大会每次递归较深才回溯
4：不能直接从rest开始枚举，自己开始想着这样会在rest=30，就不必从50开始枚举了，但事实上rest有可能远大于50，故要写min{rest,50}，这个地方查错6~8h。
5：保存上一次用的木棍长度maxn，下一次直接从min{rest，maxn}开始枚举，即当前待拼凑木棍长度 和 上一次使用的切后木棍长度 两者的较小值。比如rest=34，maxn=9或者rest=5，maxn=9都会显出作用。玄学的是，有一组数据完全由64个1和2构成，我用的min{rest,50}，按理说50直接next跳到2很快呀，结果用时1s，改成min{rest,2}，用时0.8s，改成min{rest,maxn}就0.05s了，上一次用1，这一次从2跳到1花了很长时间，看来判断2不合法2跳到1的开销在偌大的递归中也很关键。这组数据使得瓶颈突破在于maxn。
6：另一组数据59个随机分布的值，瓶颈突破在于rest，大致理解：木棍1，5，11这样，假如原来18，拼完11，剩下7，拼5，剩下2，这样，上一次拼的长度要比当前rest大很多，故瓶颈突破在于rest，这是与上组数据不同的地方。
7：最关键的两条剪枝，①当rest等于当前木棍的长度i时，如果拼不成功，就回溯，因为长度为i这个木棍迟早要拼，假如rest==i==5，用了5，剩下的不能拼成功，那么如果rest==5用2，3拼好，把5留到后面拼，同样拼不好。②如果当前要拼一根完整木棍，但用了长度为i的最后拼不好，那么这样的话，如果这次先不用i，用更小的，把i放在后面，这个i一定也拼不好。
#include<bits/stdc++.h>
using namespace std;
int n,cnt[55],l,r,next[55];
int len;
bool search(int num,int rest,int maxn)
{
if(num==0&&rest==0)return true;
if(rest==0)return search(num-1,len,l);
for(int i=min(maxn,rest);i>=1;i=next[i])if(cnt[i]) //rest可能远大于50这个问题搞了整整一天，6~8个小时。现在1:11。
{
cnt[i]--;
bool success=search(num,rest-i,i);
cnt[i]++;
if(success)return true;
if(rest==len || rest==i)return false;
}
return false;
}
void init()
{
int x;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
if(x<=50)
{
cnt[x]++;
r+=x;
l=max(l,x);
}
}
int last=0;
for(int i=1;i<=50;i++)
{
next[i]=last;
if(cnt[i])last=i;
}
}
int main()
{
freopen("input.in","r",stdin);
init();
for(len=l;len<=r;len++)if(r%len==0)
{
if(search(r/len,0,l))break;
}
cout<<len<<endl;
return 0;
}
