原题大意

给定N个数A1, A2, A3, … AN，小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大。其中AND是按位与操作。

算法分析

这题时间空间限制不太紧，暴力就可以过，但是可以用高维前缀维护最大值和次大值来做。
因为2^20可以枚举的到，而且枚举x&y的结果z，不会丢解，因为z相当于x&y的子集，就是说z是x的子集，z也是y的子集。

http://www.cnblogs.com/forever97/p/hihocoder1496.html

程序代码

#include <cstdio>
#include <algorithm>
using namespace std;
int T, n;
//高维前缀的数据结构
struct info
{
    int val[2];
    info operator + (const info & 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 info{t_val[0], t_val[1]};
    } 
}dp[1<<20+5];
int main(){
    scanf("%d", &T);
    while(T--){
        for(int i = 0; i <(1<<20);i++)
            dp[i] = info{0,0};
        int x;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &x);
            dp[x] = dp[x] + info{x,0};
        }

        for(int i = 0; i < 20; i++)
        //从左到右，从右到左没有关系
            for(int j = 0; j < (1<<20); j++)
            //从大到小，从小到大没有关系
            //为什么for循环的顺序是这样的？因为反过来状态不能更新
            //比如10011，可以到11011和10111，然后再到11111，反过来到不了11111。
                if(~j & (1<<i)) dp[j] = dp[j] + dp[j|(1<<i)];
            //设z = j,~是取反，这里是j的补集，比如10011取反是01100
            //当1<<i为00100，这个if语句能够执行，令x=j|(1<<i)，z就是x的子集，这样才满足状态转移的方程
        long long res  = 0;
        for(int i = 0; i < (1<<20); i++)
            res = max(res,1LL*i*dp[i].val[0]*dp[i].val[1]);
        printf("%lld\n", res);
    }
    return 0;
}