首页 > > 程序设计 > C/C++ >

2144 砝码称重 2

2018-06-17 22:21:12来源：未知阅读 ()

时间限制: 1 s

空间限制: 16000 KB

题目等级 : 钻石 Diamond

题目描述 Description

有n个砝码，现在要称一个质量为m的物体，请问最少需要挑出几个砝码来称？

注意一个砝码最多只能挑一次

输入描述 Input Description

第一行两个整数n和m，接下来n行每行一个整数表示每个砝码的重量。

输出描述 Output Description

输出选择的砝码的总数k，你的程序必须使得k尽量的小。

样例输入 Sample Input

3 10
5
9
1

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=n<=30，1<=m<=2^31，1<=每个砝码的质量<=2^30

分类标签 Tags 点此展开

这个题，，

非常考研剪枝能力，

除了正常的最优性剪枝

还要用后缀和剪枝。

醉了醉了。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<map>
 7 #define lli long long int 
 8 using namespace std;
 9 void read(lli &n)
10 {
11     char c='+';lli x=0;bool flag=0;
12     while(c<'0'||c>'9')
13     {c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')
15     {x=x*10+(c-48);c=getchar();}
16     flag==1?n=-x:n=x;
17 }
18 lli n,p;
19 lli a[10001];
20 lli sum2[10001];
21 map<int,bool>mp;
22 lli comp(lli a,lli b)
23 {
24     return a>b;
25 }
26 lli ans=0x7ffff;
27 void dfs(lli now,lli num,lli step,lli sum)
28 {
29     
30     if(step>ans||sum>p)
31         return ;
32     
33     if(sum==p)
34     {
35         ans=min(ans,step);
36         return ;
37     }
38     if(sum2[now]+sum<p)
39         return ;
40     if(now==n)
41         return ;
42     dfs(now+1,a[now+1],step+1,sum+a[now+1]);
43     dfs(now+1,num,step,sum);
44 }
45 int main()
46 {
47     read(n);read(p);
48     for(lli i=1;i<=n;i++)
49         read(a[i]);
50     sort(a+1,a+n+1,comp);
51     for(int i=n;i>=1;i--)
52         sum2[i]=sum2[i+1]+a[i];
53     for(lli i=1;i<=n;i++)
54         dfs(i,a[i],1,a[i]);
55     printf("%lld",ans);
56     return 0;
57 }