P1120 小木棍（搜索+剪枝）

题目链接：P1120 小木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

样例输入： 

9
5 2 1 5 2 1 5 2 1

样例输出：

6

分析：这道题一看数据范围就知道是搜索，但关键是需要剪枝。

首先我们求出所有木棍的长度和，那么原始木棍的长度一定是长度和的因子，这是显然的，然后我们就开始对每个因子进行从小到大搜索。

根据贪心性质我们可以知道优先选用长的木棍进行组装，因为短的木棍在任何情况下都可以替换等长的长的木棍，但是长的木棍在有些情况下无法替换短的木棍，所以我们首先要对木棍进行从大到小排序。

先来看一下搜索函数的参数，假如我们要枚举的长度是len，首先需要知道当前长度为len的木棍还差多少，也就是res，然后还需要知道组成当前木棍的上一节子棍的长度last，因为我们枚举的子棍是逐渐减少的，所以这个可以用于剪枝，最后一个就是当前我们还差几根长度为len的木棍就可以完整拼完了。

下面来分析一下哪些地方可以剪枝：

1.如果我们一开始拼一节长度为len的木棍，这个时候还没有放上去小木棍，那么这个时候我们就放上去还未使用过的长度最长的木棍。因为所有木棍最后都一定要用上的

2.我们可以用nx[i]标记下一个与第i根木棍长度不一致的编号，假如我们当前用第i根木棍没有拼接成功，那么如果下一根木棍跟当前木棍长度一样，那么我们也就没有必要用下一根木棍了，直接选用下一个跟当前木棍长度不一致的木棍即可

3.我们记录了组装当前木棍的剩余长度res和组成当前木棍的上一个子木棍last，那么我们下一根木棍的长度一定是小于等于两者的较小值的，查询第一个小于等于两者较小值的木棍我们可以用二分来查找

4.根据第一条剪枝我们可以知道，假如当前木棍还没有开始拼，我们优先选择未使用过且最长的木棍来进行拼接，但是如果拼接失败，那么我们没必要用更小的木棍去尝试拼接，直接返回false即可，如果要是剩余的长度等于当前木棍的长度而且还未拼接成功这就代表着我们在组装当前木棍时选取最合适子木棍依旧无法拼接成功，那么这个时候我们也是直接返回false即可。

加上上面四个剪枝就可以ac了

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=100;
int a[N],len;
bool vis[N];
int nx[N];
bool cmp(int a,int b)
{return a>b;
}
int n;
bool dfs(int res,int last,int cnt)//res记录当前这根木棍还剩的拼接长度，last记录拼接当前木棍的上一个木棍的长度，cnt记录还剩多少个木棍 
{if(res==0){if(cnt==1) return true;for(int i=2;i<=n;i++)//选择第一个没有被使用的木棍进行拼接 {if(vis[i]) continue;vis[i]=true;if(dfs(len-a[i],a[i],cnt-1)) return true;vis[i]=false;break;}}int l=1,r=n;int t=min(last,res);while(l<r)//二分找第一个可以填的位置,下一个子棍的长度一定小于等于上一根拼接该木棍的子棍长度 {int mid=l+r>>1;if(a[mid]<=t) r=mid;else l=mid+1;}	for(int i=l;i<=n;i++){if(vis[i]) continue;vis[i]=true;bool flag=dfs(res-a[i],a[i],cnt);vis[i]=false;if(flag) return true;//有一个可以了就可以退出了 if(res==a[i]||res==len) return false; i=nx[i]-1;//用第i根木棍没有拼接成功 }return false; 
}
int main()
{cin>>n;int sum=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];}sort(a+1,a+n+1,cmp);nx[n]=n+1;for(int i=n-1;i>=1;i--){if(a[i]==a[i+1]) nx[i]=nx[i+1];else nx[i]=i+1;}int ans=sum;for(len=a[1];len<=sum/2;len++)//枚举原始木棍长度{if(sum%len) continue;vis[1]=true;if(dfs(len-a[1],a[1],sum/len)){ans=len;break;}}printf("%d",ans);return 0;
}