P1120 小木棍 [数据加强版]

2018-06-17 22:20:18来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过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 }

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1186 玛丽卡

下一篇:高精确度——黄金分割数(前100位)