题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4016
题目意思:从n个数中挑选m个数,使得这m个数按位与之后结果最小,输出最小值。
For example, there are three integers 5, 6 and 7. You are asked to pick two of them. Your possible strategy is (5, 6), (5, 7) or (6, 7). The values when do bitwise and all the picked numbers together are as follows:
5 and 6 = 4
5 and 7 = 5
6 and 7 = 6
The smallest one is 4.
剪枝:
1.从当前值开始,如果选上剩下的所有,也不能小于已得最优值的话,返回。这里可以先进行一下预处理,即逆序与一下, 暂存结果。这样可以减到178ms。
2.最优值不用等到累积选到k数才更新,而是不断更新,因为与运算结果比原来两个都小,所以这也是一个剪枝。
3.预处理,从小到大排序,可想而知,先选小的,得到的最优值更接近于结果,是个强剪枝。
代码如下:
分享到:
相关推荐
HDUACM201303版_10搜索入门
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
n)⊕n, where ``⊕’’ denotes the bitwise XOR operation. Please write a program to find the smallest positive integer n that (f(n,m)?n)⊕n=k, or determine it is impossible. Input The first line of ...
搜索 dfs 解题代码 hdu1241
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1734821
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目