首页 > 代码库 > 2144 砝码称重 2
2144 砝码称重 2
时间限制: 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。