E - 吴队长征婚
Time Limit: 10000/4000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
吴队长征婚这件事因为请客而没有传出去(虽然他忘了请一个队吃饭)，于是吴队长高兴地玩起了木棒。吴队长拿了一些长度相同的木(guang)棒(gun)，随机的把它们截成了N段，每一段最长50。现在他想把这些木棒还原成原来的状态，但是他忘记了原来的木棒有多少根，也忘记了每一根有多长。请帮助他设计一个程序，帮他计算之前木棒可能的最小长度。输入数据保证每一段木棒长度都大于0。
Input
输入有多组数据，每组数据分为两行。
第一行一个整数N，表示截断之后木棒的个数。1≤N≤64
第二行N个整数，表示截断之后的每一段小木棒的长度。 当N=0时，表示输入结束。
Output
每组数据输出一个整数占一行，表示原木棒可能的最小长度。
Sample input and output
9 | 6 |
解题报告:
先对木棒进行降序排序
我们设计几个剪枝:
1.每截木棒肯定是和的约数
2.若正在拼某截的第一段，而此时最大的木棒用不上，直接回溯
3.若拼完某截木棍后，剩下的无法拼成，直接回溯
4.若该木棍用不上，之后所有长度相同的木棍也用不上
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int tn,tlen,len[],n;
bool use[]; bool cmp(int x,int y)
{
return x > y;
} bool dfs(int cur,int res,int pos)
{
if (res == tlen)
{
res = ;
pos = ;
cur ++;
}
if (cur == tn)
return true;
for(int i = pos;i < n ; ++ i)
if (!use[i] && res + len[i] <= tlen)
{
use[i] = true;
if (res + len[i] == tlen)
{
if (!dfs(cur+,,))
{
use[i] = false;
return false;
}
return true;
}
else
{
if (dfs(cur,res+len[i],i+))
return true;
use[i] = false;
if (res == )
return false;
for(int j = i + ; j < n ; ++ j)
if(len[i] == len[j])
i++;
}
}
return false;
} int main(int argc , char * argv[])
{
while(scanf("%d",&n) && n)
{
int sum = ;
for(int i = ; i < n ; ++ i)
{
scanf("%d",&len[i]);
sum += len[i];
}
memset(use,false,sizeof(use));
sort(len,len+n,cmp);
int ok = ;
for(int i = len[] ; i <= sum / ; ++ i)
if (sum % i == )
{
tn = sum / i;
tlen = i;
if(dfs(,,))
{
cout << i << endl;
ok = ;
break;
}
}
if(!ok)
cout << sum << endl;
}
return ;
}