洛谷1120 小木棍
题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入输出格式
输入格式：
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
输出格式：
输出文件仅一行，表示要求的原始木棍的最小可能长度
输入输出样例
输入样例#1：
9
5 2 1 5 2 1 5 2 1
输出样例#1：
6
【思路】
枚举+回溯法构造判定。
不难想到从小到大枚举原木棍的长度，但是长度最大可以为300,太大了，我们换而从小到大枚举原木棍根数num，只要可以构造出num根相同长度len的木棍则完成任务。
如何判定能够构造成功？回溯法。
先对数据由大到小sort，这样在搜索的时候会先尝试长度大的木棍，显然先选大长度的木棍是优于选小长度的，因为小长度会更有用（可以组合的更多）。
以目前组装的第几根木棍d、目前组装的长度nowlen以及该从哪开始枚举木棍的下标nowi为状态，搜索是否能够使d==num+1即可。
剪枝：
1、 木棍数目枚举范围：最大为 长度和/最大长度
2、 木棍数目是否符合要求：木棍数目为总长度的约数。
3、 后缀和判断解不可行。
4、 Nowi的使用减少同一根小棒的枚举
5、 每次组装新的木棍的时候人为选择最长的木棍（加速枚举中nowlen+a[i]<len的判断，否则会多拓展一层）
【代码】
#include<iostream>
#include<algorithm>
using namespace std; const int maxn = +; int a[maxn],cnt[maxn];
int len,num,n;
int suff_s[maxn]; inline bool cmp(const int& a,const int& b) {
return a>b;
}
bool dfs(int d,int nowlen,int nowi) {
if(d==num) return true; if(len-nowlen > suff_s[nowi]) return false; for(int i=nowi;i<n;i++) if(cnt[a[i]]) {
if(a[i]+nowlen < len) {
cnt[a[i]]--;
if(dfs(d,nowlen+a[i],i+)) return true;
cnt[a[i]]++;
}
if(a[i]+nowlen==len) {
cnt[a[i]]--;
int j;
for(j=;j<n;j++) if(cnt[a[j]]&&a[j]<len) break;
cnt[a[j]]--;
if(dfs(d+,a[j],j+)) return true;
cnt[a[j]]++;
cnt[a[i]]++;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
int tot=,x,_max=,maxx=;
for(int i=;i<n;i++) {
cin>>x;
if(x<=) {
a[tot++]=x;
suff_s[tot-]=x;
_max+=x;
maxx=max(maxx,a[tot-]);
cnt[x]++;
}
}
n=tot;
for(int i=n-;i>=;i--) suff_s[i] += suff_s[i+];
sort(a,a+n,cmp);
int t=_max/maxx; if(t>n) t=n;
cnt[a[]]--;
for(num=t;num>=;num--) if(_max%num==) {
len=_max/num;
if(dfs(,a[],)) {
cout<<len;
break;
}
}
return ;
}