首页 > 代码库 > hihocoder 1496：寻找最大值（高维前缀最大次大值）
hihocoder 1496：寻找最大值（高维前缀最大次大值）
【题目链接】 https://hihocoder.com/problemset/problem/1496
【题目大意】
给定N个数A1, A2, A3, ... AN,
从中找到两个数Ai和Aj(i≠j)使得乘积Ai*Aj*(Ai&Aj)最大
【题解】
我们可以枚举x&y的结果z，找出两个数x&y==z使得x*y最大，更新答案即可，
条件可以被削弱为z为x&y的子集，这种条件放缩不会导致最优解的丢失，
z为x&y的子集等价于z为x的子集并且z为y的子集。
那么我们只要找出以z为子集的最大值和次大值，然后枚举z即可计算出答案。
复杂度O(k*2^k).
【代码】
#include <cstdio>#include <algorithm>using namespace std;struct data{ int val[2]; data operator +(const data &rhs)const{ int t_val[2]={val[0],val[1]}; for(int i=0;i<2;i++){ if(rhs.val[i]>t_val[0]){ t_val[1]=t_val[0]; t_val[0]=rhs.val[i]; }else if(rhs.val[i]>t_val[1])t_val[1]=rhs.val[i]; }return data{t_val[0],t_val[1]}; }}dp[(1<<20)+10];int T,n;int main(){ scanf("%d",&T); int all=1<<20; while(T--){ for(int i=0;i<all;i++)dp[i]=data{0,0}; scanf("%d",&n); for(int i=1,x;i<=n;i++){ scanf("%d",&x); dp[x]=dp[x]+data{x,0}; } for(int i=0;i<20;i++) for(int j=0;j<all;j++) if(~j&(1<<i))dp[j]=dp[j]+dp[j|(1<<i)]; long long ans=0; for(int i=0;i<all;i++)ans=max(ans,1LL*i*dp[i].val[0]*dp[i].val[1]); printf("%lld\n",ans); }return 0;}hihocoder 1496：寻找最大值（高维前缀最大次大值）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。