专栏首页数据结构与算法P1120 小木棍 [数据加强版]

P1120 小木棍 [数据加强版]

题目描述

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ3624: [Apio2008]免费道路(最小生成树)

    这棵树上有一些0边是必须要选的,我们先把他们找出来,如果数量$\geqslant k$显然无解

    attack
  • cf250D. The Child and Sequence(线段树 均摊复杂度)

    复杂度不知道是一个log还是两个log,大概是两个吧(线段树一个+最多改log次。)

    attack
  • 洛谷P3586 [POI2015]LOG(贪心 权值线段树)

    attack
  • 算法复杂度O(logn)详解

    由于cnt每次在乘以2之后都会更加逼近n,也就是说,在有x次后,cnt将会大于n从而跳出循环,所以

    233333
  • LWC 53:694. Number of Distinct Islands

    LWC 53:694. Number of Distinct Islands 传送门:694. Number of Distinct Islands Probl...

    用户1147447
  • BZOJ3624: [Apio2008]免费道路(最小生成树)

    这棵树上有一些0边是必须要选的,我们先把他们找出来,如果数量$\geqslant k$显然无解

    attack
  • cf250D. The Child and Sequence(线段树 均摊复杂度)

    复杂度不知道是一个log还是两个log,大概是两个吧(线段树一个+最多改log次。)

    attack
  • 洛谷P3586 [POI2015]LOG(贪心 权值线段树)

    attack
  • E Hilbert Sort 分治

    用户2965768
  • LeetCode Contest 181

    遍历除数的时候从1到sqrt(nums[i]) 10000*sqrt(100000) 是不会超时的

    ShenduCC

扫码关注云+社区

领取腾讯云代金券