ARC100 E Or Plus Max

其中，\(f[k]\)表示递推到第i位的最大值。
那么，\(f[k]\)显然是可以从\(f[k-1]\)递推来的。
这时候只要考虑\(i|j==k\)的值。
枚举k的子集，求最大值。
这样做是\(O(松松松)\)的。
考虑优化。
我们可以发现，对于k的每一个子集，它的子集的最大值是已经求过的。
那么我们只需要考虑枚举每一个k子集的一部分，可以考虑每一次把它反与上一个\(2^l\)，并求Max和次Max。
这样有解，复杂度\(O(n*2^n)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Swap(_A,_B) ((_A)^=(_B)^=(_A)^=(_B))
using namespace std;
//mx[i][0]表示最大值，mx[i][1]表示次大值。 
int f[1<<18],n,a[1<<18];
int nw,mxx,lmxx,sa,sb,st;
struct data{
    int v;
    int nm;
    bool operator ==(const data &x)const{
        return this->v==x.v&&this->nm==x.nm;
    }
}lst[40],mx[1<<18][2];
inline bool cmp(const data &x,const data &y){
    return x.v>y.v;
}
//处理第k个数，它的最大值和次大值。 
int wrk(int k){
    nw=0,mxx=0,lmxx=0,sa=-1,sb=-1,st=0;
    lst[++st]=(data){a[k],k};
    for(int i=0;(1<<i)<=k;++i){
        if((k>>i)&1){
            nw=k^(1<<i);
        }else{
            continue;
        }
        lst[++st]=mx[nw][0];
        lst[++st]=mx[nw][1];
    }
    sort(lst+1,lst+1+st,cmp);
    unique(lst+1,lst+1+st);
    mx[k][0]=lst[1],mx[k][1]=lst[2];
    return mx[k][0].v+mx[k][1].v;
}
void init(){
    scanf("%d",&n);
    const int MAX=1<<n;
    for(int i=0;i<MAX;++i){
        scanf("%d",&a[i]);
    }
    f[0]=0,mx[0][0].v=a[0],mx[0][1].v=0,mx[0][0].nm=0,mx[0][1].nm=-1;
    for(int k=1;k<MAX;++k){
        f[k]=wrk(k);
        f[k]=Max(f[k],f[k-1]);
        printf("%d\n",f[k]);
    }
}
int main(){
    init();
    return 0;
}