首页 > 代码库 > wikioi 2144 分步二进制枚举+map记录
wikioi 2144 分步二进制枚举+map记录
题目描述 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
思路:这题刚开始用了搜索,不机智T了又WA了。然后重新回到二进制枚举上来吧。刚开始读题的时候想用二进制枚举了,但是无奈n<=30,2^30早就T了,所以用不了二进制枚举。
搜索又T又WA的,然后只好看了一下解题报告。里面说了用二进制枚举,但是分块来枚举就不会T了。呀!真是太机智了大神们!!因为最多有30个数,而他们的组合都会很大的,但是如果我们先搞先n/2个数的组合,然后再搞后(n+1)/2个数的组合的话,然后再把前后合成,就不会T了,而且也可以保证前后组合后与标准的组合是一样的。分治的思想。
二进制又进步了很多,以前是20以下的才敢二进制枚举,现在20以上的用了分治思想后也可以用二进制枚举了,历害!!!!
#include<iostream> #include<cstdio> #include<algorithm> #include<map> using namespace std; int main() { int n,m,a[33],i,j,ans=1000000007; map<int,int>mm; cin>>n>>m; for(i=0;i<n;i++) cin>>a[i]; for(i=1;i<(1<<(int)(n/2+1));i++) { int sum=0,cnt=0; for(j=0;j<n/2;j++) if(i&(1<<j)) sum+=a[j],cnt++; if(!mm[sum]||cnt<mm[sum]) mm[sum]=cnt; } if(mm[m]) ans=mm[m]; for(i=1;i<(1<<(int)((n+1)/2+1));i++) { int sum=0,cnt=0; for(j=0;j<(n+1)/2;j++) if(i&(1<<j)) sum+=a[j+n/2],cnt++; if(sum==m) ans=min(ans,cnt); if(mm[m-sum]) ans=min(ans,mm[m-sum]+cnt); } cout<<ans<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。