乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。
现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。
输入格式:
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数,其中N≤65
(管理员注:要把超过50的长度自觉过滤掉,坑了很多人了!)
第二行为N个用空个隔开的正整数,表示N根小木棍的长度。
输出格式:
输出文件仅一行,表示要求的原始木棍的最小可能长度
输入样例#1:
9
5 2 1 5 2 1 5 2 1
输出样例#1:
6
这题挺坑的,数据量太大了,无奈看了看题解
题解加了许多剪枝
1.从大到小排序
2.每次枚举的时候从上一个结束的地方枚举
3.相同长度不枚举
4.如果是当前的长度不能构成答案需要的长度,直接退出
还有就是二分答案貌似写不出来。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 const int MAXN=71;
8 void read(int &n)
9 {
10 char c='+';int x=0;bool flag=0;
11 while(c<'0'||c>'9')
12 {c=getchar();if(c=='-')flag=1;}
13 while(c>='0'&&c<='9')
14 {x=x*10+(c-48);c=getchar();}
15 flag==1?n=-x:n=x;
16 }
17 int a[MAXN];
18 int num=0;
19 int n,p;
20 int tot=0;
21 int k;
22 int vis[MAXN];
23 int comp(int a,int b)
24 {return a>b;}
25 bool dfs(int now,int bg,int have,int need)
26 // 需要拼接的长度 开始的值 已经拼好的组数 需要拼接的长度
27 {
28 if(have==k)
29 return 1;
30 if(now==0)
31 if(dfs(need,1,have+1,need))
32 return 1;
33 for(int i=bg;i<=num;i++)
34 {
35 if(vis[i]==0&&a[i]<=now)
36 {
37 vis[i]=1;
38 if(dfs(now-a[i],i+1,have,need))
39 return 1;
40 vis[i]=0;
41 if(now==need||now==a[i])break;
42 while(a[i+1]==a[i])
43 i++;
44 }
45 }
46 return 0;
47 }
48 int main()
49 {
50 //freopen("sticka.in","r",stdin);
51 //freopen("sticka.out","w",stdout);
52 read(n);
53 for(int i=1;i<=n;i++)
54 {
55 read(p);
56 if(p<=50)
57 {
58 a[++num]=p;
59 tot+=p;
60 }
61 }
62 sort(a+1,a+num+1,comp);
63 for(int i=a[1];i<=tot;i++)
64 {
65 if(tot%i==0)
66 {
67 k=tot/i;
68 if(dfs(i,1,0,i))
69 {
70 printf("%d",i);
71 return 0;
72 }
73 }
74
75 }
76 return 0;
77 }