木棒
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 118943 Accepted: 27429
Description
乔治拿来一组等长的木棒。将它们随机地砍断。使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。
Input
输入包括多组数据,每组数据包括两行。
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 118943 Accepted: 27429
Description
乔治拿来一组等长的木棒。将它们随机地砍断。使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。
Input
输入包括多组数据,每组数据包括两行。
第一行是一个不超过64的整数,表示砍断之后共同拥有多少节木棍。第二行是截断以后。所得到的各节木棍的长度。在最后一组数据之后,是一个零。
Output
为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a, int b )
{
return a>b;
}
int sticks[100];
bool used[100];
int n, StickLen, len;
bool dfs(int i,int l,int t)
//i为当前试取的棍子序号,l为要拼成一根完整的棍子还须要的长度,t初值为全部棍子总长度
{
if(l==0) {
t-=len;
if(t==0)return true;
for(i=0; used[i]; ++i);
//剪枝1:搜索下一根大棍子的时候,找到第一个还没有使用的小棍子開始
used[i]=1;
//因为排序过,找到的第一根肯定最长,也肯定要使用,所以从下一根開始搜索
if(dfs(i+1,len-sticks[i],t))return true;
used[i]=0;
t+=len;
} else {
for(int j=i; j<n; ++j) {
if(j>0&&(sticks[j]==sticks[j-1]&&!used[j-1]))
//剪枝2:前后两根长度相等时,假设前面那根没被使用。
//也就是由前面那根開始搜索不到正确结果,那么再从这根開始也肯定搜索不出正确结果,此剪枝威力较大
continue;
if(!used[j]&&l>=sticks[j]) {
//剪枝3:最简单的剪枝。要拼成一根大棍子还须要的长度L>=当前小棍子长度,才干选用
l-=sticks[j];
used[j]=1;
if(dfs(j,l,t))return true;
l+=sticks[j];
used[j]=0;
if(sticks[j]==l)
//剪枝4:威力巨大的剪枝,程序要执行到此处说明往下的搜索失败。
//若本次的小棍长度刚好填满剩下长度。可是后面的搜索失败,则应该返回上一层
break;
}
}
}
return false;
}
int main()
{
int i, totalLen;
bool flag;
while(scanf("%d",&n),n) {
totalLen = 0;
for(i=0; i<n; ++i) {
scanf("%d",&sticks[i]);
totalLen += sticks[i];
}
sort(sticks, sticks+n, cmp);
memset(used, 0, sizeof used );
flag = false;
for(StickLen = sticks[0]; StickLen <=totalLen/2; ++StickLen) {
len = StickLen;
if(totalLen % StickLen == 0)
if(dfs(0, StickLen, totalLen) ) {
flag= true;
printf("%d\n",StickLen);
break;
}
}
if(!flag) {
printf("%d\n",totalLen);
}
}
return 0;
}