首页 > 代码库 > hihocoder1496(高维前缀和)
hihocoder1496(高维前缀和)
题意:给定N个数A1, A2, A3, ... AN,小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大。其中AND是按位与操作。
第一行一个整数N(1<=N<=100,000)
第二行N个整数A1, A2, A3, ... AN (0 <= Ai <2^20)
分析:
尝试枚举and值z,那么问题就变成了找寻最大的x*y,使得x&y==z
把这个要求放宽一点,我们来寻找z是x&y子集的情况(这样肯定不会丢掉整体最优解)
这意味着z是x的子集,且z是y的子集
问题就变成求包含z的集合中,最大的数字和最小的数字
这就是个高维前缀和维护问题了,dp解决
hihocoder1496(高维前缀和)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。