http://noi.openjudge.cn/——4.7算法之搜索——13:Sticks
题目
13:Sticks
总时间限制: 1000ms 内存限制: 65536kB
描述
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
输入
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
输出
The output should contains the smallest possible length of original sticks, one per line.
样例输入
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
样例输出
6
5
翻译
描述：
乔治拿起相同长度的棍子，随机切割，直到所有部分的长度都不超过50个单位。
现在他想把棍子恢复原状，但他忘了自己原来有多少根棍子，原来有多长。
请帮助他设计一个程序，计算这些棍子的最小原始长度。
所有以单位表示的长度都是大于零的整数。
输入：
输入包含2行的块。第一行包含切割后的棒部件数量，最多有64根棒。
第二行包含由空格分隔的部分的长度。文件的最后一行包含零。
输出：
输出应包含尽可能短的原始棒，每行一根。
代码（借鉴网友代码）
#include <bits/stdc++.h>
using namespace std;
struct node{
int x,id;
}s[65];
int n,x;
bool cmp(node a,node b){
return a.x>b.x;
}
void view(string sx,int aim,int he){
cout<<sx<<“\t”<<aim<<“\t”<<he<<endl;
for(int i=1;i<=n;i++)cout<<i<<“\t”;cout<<endl;
for(int i=1;i<=n;i++)cout<<s[i].x<<“\t”;cout<<endl;
for(int i=1;i<=n;i++)cout<<s[i].id<<“\t”;cout<<endl;
}
bool go(int aim,int he,int num,int id,int x){
//目标值，现在和，木条数量，序号，现在位置
if(aim= =he&&num= =n){
//cout<<“ok\n”;
return 1;}
if(he= =0){//新一组
for(int i=1;i<=n;i++){
if(s[i].id)continue;
s[i].id=id;
//view(“新一组”,aim,he);
if(go(aim,s[i].x,num+1,id,0)){
//cout<<i<<“该线成功\n”;
return 1;}
else{
s[i].id=0;
//cout<<i<<“该线失败\n”;
return 0;}
s[i].id=0;
}
//cout<<“全部失败\n”;
return 0;
}
if(aim= =he){//满了一组
//view(“满一组”,aim,he);
if(go(aim,0,num,id+1,0))return 1;
else return 0;
}
for(int i=x+1;i<=n;i++){
if(s[i].x+he>aim||s[i].id)continue;
if(s[i-1].x==s[i].x&&!s[i-1].id)continue;
s[i].id=id;
//view(“下一个”,aim,he);
if(go(aim,s[i].x+he,num+1,id,i))return 1;
s[i].id=0;
}
return 0;
}
int main(){
//freopen(“data.cpp”,“r”,stdin);
while(cin>>n&&n){
int m,he=0;
for(int i=1;i<=n;i++){
cin>>x;s[i]=node{x,0};he+=x;
}
//view(“排序前”,0,0);
sort(s+1,s+n+1,cmp);
//view(“排序后”,0,0);
for(m=s[1].x;m<=he;m++){
if(he%m!=0)continue;
for(int i=1;i<=n;i++)s[i].id=0;
//cout<<“m:”<<m<<endl;
if(go(m,0,0,1,0))break;
}
cout<<m<<endl;
}
return 0;
}
小结
- 最初一样长的多根木条被随机切成了很多个，问原来的木条有多长。
- 切割后所得最长的木条是原木条最短长度，切割所得所有木条长度和是原木条最大长度。
- 原木条一样长，所以长度和必须能被原木条整除。
- 要做的就是递归回溯深搜分组，每组木条长度和等于设定的原木长度。
- 很容易超时，该程序的得力点是分层递归
分层递归
- 如果选中木条长度和等于零，he==0，就是说开始选新的一组，for(int i=1;i<=n;i++)go(aim,s[i].x,num+1,id,0)。从头开始选，该木条的长度就是木条和。
- 凑够了预期的长度，he==aim，选完了一组，并开始新的一组，go(aim,0,num,id+1,0)。木条和从零开始。
- 该组通过步骤1选完第一根后开始继续选，for(int i=x+1;i<=n;i++)从剩余的木条里选，go(aim,s[i].x+he,num+1,id,i)。
- 其中的玄妙还是理解不充分，望网友们给与建议。
一层递归（超时）
#include <bits/stdc++.h>
using namespace std;
struct node{
int x;
int k;
}d[65];
/*
一样的木条被随机切分成n根，问本来的木条最短有多长
木条要切成最长5
从5开始一个个试
和超过5就剪枝，
算过的要标记
*/
int n,x,ans;
bool over(){
for(int i=1;i<=n;i++)if(!d[i].k)return 0;
return 1;
}
void view(string s,int he,int limit){
cout<<s<<“\t”<<he<<“,”<<limit<<endl;
for(int i=1;i<=n;i++)cout<<i<<“\t”;cout<<endl;
for(int i=1;i<=n;i++)cout<<d[i].x<<“\t”;cout<<endl;
for(int i=1;i<=n;i++)cout<<d[i].k<<“\t”;cout<<endl;
cout<<endl;
}
bool go(int id,int he,int limit){
if(over()&&he!=limit){cout<<“小了\n\n”;return 1;}//
if(over()&&he= =limit){cout<<“ok\n”;return 0;}//
if(!over()&&he= =limit){he=0;id++;}//
for(int i=1;i<=n;i++){
if(d[i].k)continue;//用过的不能再用
if(d[i].x+he>limit)continue;//超过最初长度，就不能要
d[i].k=id;
view(“递归”,d[i].x+he,limit);
if(!go(id,d[i].x+he,limit))return 0;
d[i].k=0;
}
return 1;
}
int main(){
freopen(“data.cpp”,“r”,stdin);
while(cin>>n&&n){
for(int i=1;i<=n;i++){
cin>>x;d[i]=node{x,0};
}
view(“开始”,0,0);
int m=5;
while(go(1,0,m)){
m++;//m不是同样长度原木条的长度，就增加
for(int i=1;i<=n;i++)d[i].k=0;
view(“----------------加一个”,0,m);
}
cout<<m<<endl;
}
return 0;
}