问题 C: 【例题3】小木棍
时间限制:1 Sec内存限制:128 MB
提交:7解决:5
[提交][状态][讨论版][命题人:add_cy]
题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60。
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
输出
输出文件仅一行，表示要求的原始木棍的最小可能长度。
样例输入
9
5 2 1 5 2 1 5 2 1
样例输出
6
从最优性方面：
1.设所有木棍长度和为sum，那么原长度（也就是需要输出的长度）一定能够被sum整除，这样得到的木棍根数才是整数
2.木棍原来的长度一定不小于所有木棍中最长的那根
综上两点，可以确定原木棍的长度len在最长木棍的长度maxlen和sum之间取值，且sum能被len整除。所以在搜索原木棍的长度时，可以从砍过以后所有木棍中最长的长度开始，每次增加长度后，必须能整除sum。这样可以有效优化程序。
从可行性方面：
1.短木棍更加灵活，长木棍受到的限制更大，所以可以对输入的所有木棍按长度从大到小排序。
2.在砍断后的排好序的木棍中，当用木棍i拼合原始木棍时，可以从i+1的木棍开始往后搜，因为i前面的木棍已经用过了
3.从当前最长长度的木棍开始搜，如果拼不出当前设定的原木棍长度len则直接返回，换一个原始木棍长度len
4.相同长度的木棍不要搜索多次.用当前长度的木棍搜下去得不出结果时，用一支同样长度的还是得不到结果，所以可以提前返回
5.判断搜到的几根木棍组成的长度是否大于原始长度len，如果大于没必要搜下去，可以提前返回
6.判断当前剩下的木棍根数是否够拼成木棍，如果不够，肯定拼合不成功，直接返回
7.找到结果后，在能返回的地方马上返回到上一层的递归处
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,m,len,sum=0,maxlen=0,flag;
int a[61],visit[61];
int cmp(int a,int b)
{
return a>b;
}
void dfs(int k,int last,int rest)//k为第k根木棍，last为第k根上一节木棍编号；rest为第k根木棍还需要的长度
{
int i;
if(k==m){flag=1;return;}//木棍根数达到要求，剪枝
if(rest==0)开始下一根木棍
{
for(i=0;i<n;i++)//查找一个未访问过的木棍节，剪枝
if(!visit[i]){visit[i]=1;break;}
dfs(k+1,i,len-a[i]);
}
for(i=last+1;i<n;i++)//当前剩下的木棍节，可行性剪枝2
{
if(!visit[i]&&a[i]<=rest)//木棍节为被访问过并且比需要的木棍长度短，可行性剪枝5
{
visit[i]=1;//置当前的木棍节为已使用
dfs(k,i,rest-a[i]);
visit[i]=0;//回溯
int j=i;
while(i<n&&a[i]==a[j])i++;//防止相同长度的木棍搜索多次，可行性剪枝4
if(i==n-1)return;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)//依次读入每根木棍的长度
{
cin>>a[i];
sum+=a[i];//求所有木棍的长度和
if(a[i]>maxlen)maxlen=a[i];//求最长木棍即枚举的最小值
}
sort(a,a+n,cmp);//对木棍按从大到小排序，可行性剪枝1
for(int i=maxlen;i<=sum;i++)//枚举原始木棍的长度，最优性剪枝
{
if(sum%i==0)//sum能被原木棍长度len整除
{
memset(visit,0,sizeof(visit));
visit[0]=1;
len=i;//保存每根木棍的长度
m=sum/i;//记录木棍的根数
flag=0;
dfs(1,0,len-a[1]);
if(flag)
{
cout<<len<<endl;
break;
}
}
}
return 0;
}
| 
转播
