首页 > 代码库 > 2144 砝码称重 2

2144 砝码称重 2

2024-10-14 00:07:03   209人阅读

 时间限制: 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

2

数据范围及提示 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 }

 

 

2144 砝码称重 2


联系
我们