codevs 3498 小木棍

QAQ都这么晚了才想起来开博客
开始第一篇博客~

codevs 3498 小木棍

题目描述 Description：

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过100。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入描述 Input Description：

输入文件共有二行。
第一行为一个单独的整数N表示看过以后的小木柜的总数，其中N≤60，第二行为N个用空个隔开的正整数，表示N跟小木棍的长度。

输出描述 Output Description：

输出文件仅一行，表示要求的原始木棍的最小可能长度。

样例输入 Sample Input：

9
5 2 1 5 2 1 5 2 1

样例输出 Sample Output：

6

数据范围及提示 Data Size & Hint：

N<=60

–> 一道奇怪的搜索题，看起来无从下手，用了两个bool函数实现，不过（日常吐槽codevs），明明有两组数据本地输出正确，lj codevs 判我错，23333不管啦反正对了就行啦
|
√上代码

#include
#include
#include
#include
#include
#include
using namespace std;int N,maxn,sum,ans;
int len[100];
bool used[100];bool cmp(int a,int b)
{return a>b;
}
bool dfs(int l,int summ,int last)
{if(l==summ) return true;if(lreturn false;for(int i=last;i<=N;++i){if(!used[i]){if(dfs(l,summ+len[i],i+1)){used[i]=1;return true;}}}
}
bool judge(int l)
{for(int i=1;i<=N;++i)if(!used[i]&&!dfs(l,len[i],i+1)) return false;return true;
}
int main()
{scanf("%d",&N);for(int i=1;i<=N;++i) { scanf("%d",&len[i]);if(i==1) maxn=len[i];maxn=max(maxn,len[i]);sum+=len[i];}sort(len+1,len+N+1,cmp);for(int i=maxn;i<=sum;++i){if(sum%i) continue;memset(used,0,sizeof(used));if(judge(i)) {ans=i;break;}}printf("%d",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！