题解 P1120 【小木棍 ［数据加强版］】
虽说这数据加强，但原版是紫题，原版
废话不多说，直接开始
这题显然是一道搜索题（标签上写了）
无优化搜索
从小到大枚举答案（有个小优化，如果和不能整除此答案就跳过）
设原始木棍根数为cnt（cnt=sum/len）
三个状态
1.已经拼好的木棍根数
2.当前长度
3.使用情况
我们每次搜索只需找到尚未使用的木棍（来尝试拼接），此时搜索一下新的状态
两个边界
1.成功拼好（可以输出答案了）
2.无法拼接（返回上次拼接状态）
无优化搜索完结撒花
虽不AC,却不用动脑子的好方法！！！
有优化搜索
搜索的优化（众所皆知）
1.优化搜索顺序（此题需要）
2.排除等效冗余（此题需要）
3.可行性剪枝
4.最优性剪枝
5.记忆化搜索
优化搜索顺序！
我们可以将长度从大到小排序，优先尝试一下长的木棍
可以优化的原因：
如图所示(虽然有点丑)
我们从长的木棍开始合并或是从短的木棍开始合并长度一致，因此只需搜索其中一种
排除等效冗余
1.假设长度为x的木棍拼接失败，那么和为x的一堆木棍（一根都是如此）拼接也必然失败（状态和前面的状态一致）
2.如果已拼好的木棍长度为x，那么如果长度为y的无法向此拼接。下一堆已拼好的木棍如果长度也为x，y也一定不能向此拼接
3.用一根木棍总比用一堆木棍好（搜索之贪心）
完整代码：code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
ll r=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&(c!='-')) c=getchar();
if(c=='-') f=-1,c=getchar();
while(c>='0'&&c<='9') r=r*10+c-'0',c=getchar();
return r*f;
}
ll a[101],v[101],n,len,cnt;
bool dfs(ll stick,ll cab,ll last)
{
if(stick>cnt) return true;
if(cab==len) return dfs(stick+1,0,1);//往下一个搜
ll failess=0;
for(int i=last;i<=n;i++)
if(!v[i]&&cab+a[i]<=len&&failess!=a[i])
{
v[i]=1;
if(dfs(stick,cab+a[i],i+1)) return true;
failess=a[i];
v[i]=0;
if(cab==0||cab+a[i]==len) return false;
}
return false;
}
ll cmp(ll a,ll b)
{
return a>b;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
n=read();
ll sum=0,val=0;
for(int i=1;i<=n;i++)
{
ll b=read();
if(b>50) continue;
a[i]=b;
sum+=a[i];
val=max(val,a[i]);
}
sort(a+1,a+n+1,cmp);
for(len=val;len<=sum;len++)
{
if(sum%len) continue;
cnt=sum/len;
memset(v,0,sizeof(v));
if(dfs(1,0,1)) break;
}
cout<<len<<endl;
return 0;
}