当前位置：首页 > news >正文

P1120 小木棍［数据加强版］

news 来源：原创 2024/5/3 7:29:54

题目描述

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