oj小木棍问题
Description
乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50 。
现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。
Input
第一行为一个单独的整数 N表示砍过以后的小木棍的总数。
第二行为 N个用空格隔开的正整数,表示 N根小木棍的长度。
Output
输出仅一行,表示要求的原始木棍的最小可能长度。
Sample Input
9
5 2 1 5 2 1 5 2 1
Sample Output
6
More Info
1<=N<=60
主要思路:dfs、剪枝
先寻找可能满足条件的从小到大dp,看已知的n段小木棍能否拼成tot/i 段i长的小木棍,如果能则输出当前i,结束程序。如果均不能则输出tot。(思路来源一位dalao)
#include<stdio.h>
#include<stdlib.h>
int max,min=100,book[51];
void dfs(int rec,int sum,int lon,int now,int next)
{
int i;
if(rec==0)
{
printf("%d",lon);
exit(0);
}
while(book[next]==0)//如果没有接下来要拼凑的长度的木棍
next--;//继续寻找更短的木棍
if(lon==sum)//如果成功利用小木棍拼成lon长的木棍
{
dfs(rec-1,0,lon,next,next);//成功拼成一段lon,从剩下的最长的木棍开始拼lon
return;//拼法错误,返回
}
if(now>next)
now=next;//防止now长的木棍不存在
if(now>lon-sum)//将现存的最长的与拼成lon还需要的长度比较
i=lon-sum;
else
i=now;
for(;i>=min;i--)
{
if(book[i]&&i+sum<=lon)
{
book[i]--;//s使用i长的木棍
dfs(rec,sum+i,lon,i,next);
book[i]++;// 拼法错误取消使用i
if(i+sum==lon||sum==0)//如果已经满足这两个条件则跳出循环(可能lon不满足,与i无关)
break;
}
}
}
int main()
{
int tot=0,i,n,x;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&x);
book[x]++;//代替排序
if(min>x)
min=x;
if(max<x)
max=x;
tot+=x;
}
for(i=max;i<=tot;i++)//木棍长度一定>=最长的一段
if(tot%i==0)//剪枝
dfs(tot/i,0,i,max,max);
printf("%d",tot);
return 0;
}