P1120 小木棍［数据加强版］

题目

题目描述

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入输出格式

输入格式：

共二行。

第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中

（管理员注：要把超过

第二行为

输出格式：

一个数，表示要求的原始木棍的最小可能长度

输入输出样例

输入样例#1：复制

9
5 2 1 5 2 1 5 2 1

输出样例#1：复制

说明

2017/08/05

数据时限修改：

-#17 #20 #22 #27 四组数据时限

-#21 #24 #28 #29 #30五组数据时限

其他时限改为

分析

很显然，是一道搜索dfs
所以我们现在就要考虑如何优化
首先，我们需要去除50的
进行排序，排序的目的是，到了后面如果加上当前我的最大值还是不够的话就return
然后，我们的循环就是肯定从最大的一根木棍到tot/2（因为如果是到tot那么只有可能就是只有一根）
因为每段木棍都是整数，所以我们一定是要成tot的倍数
最后因为我们是找最小值，出现第一个个数乘以公约数==tot 直接输出即可

代码

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 using namespace std;
 5 int a[10001],cnt,tot,maxx;
 6 int used[10001];
 7 bool cmp(int x,int y) {return x>y;}
 8 void dfs(int ans,int sum,int gcd,int now)
 9 {
10     if (gcd*sum==tot){cout<<gcd; exit(0);}
11     if (ans==gcd) {dfs(0,sum+1,gcd,1); return;}
12     if (gcd<ans+a[cnt]) return;
13     for (int i=now;i<=cnt;i++)
14     {
15         if (!used[i]&&ans+a[i]<=gcd)
16         {
17             used[i]=1;
18             dfs(ans+a[i],sum,gcd,i+1);
19             used[i]=0;
20             if (ans+a[i]==gcd||ans==0) break;
21             while(a[i]==a[i+1]) i++;
22         }
23     }
24 }
25 int main ()
26 {
27     int n;
28     cin>>n;
29     for (int i=1,x;i<=n;i++)
30     {
31         cin>>x;
32         if (x<=50)
33         {
34             a[++cnt]=x;
35             tot+=x;
36             maxx=max(x,maxx);
37         }
38     }
39     sort(a+1,a+cnt+1,cmp);
40     for (int i=maxx;i<=tot/2;i++)
41     {
42         if (tot%i==0)
43           dfs(0,0,i,0);
44     }
45     cout<<tot;
46 }

为何要逼自己长大，去闯不该闯的荒唐

P1120 小木棍 ［数据加强版］

题目