题解 P4310 【绝世好题】

winxp_qwq · 2018-03-12 17:24:27 · 题解

其实就直接dp就好了

令dp[i]表示数列到目前为止最后一项第i位为1的最大子序列长度，每读入一个数时就大力转移。一个数可以被它所有的二进制位的dp值转移，然后把它转移到它的所有二进制位的dp值上。

复杂度nlogn

#include <bits/stdc++.h>
using namespace std;
int dp[32];
int main(){
    int n;
    scanf("%d",&n);
    int a,b,c,i,j,k,ans=0;
    for(a=1;a<=n;a++)
    {
        scanf("%d",&b);
        k=1;
        for(c=0;c<=30;c++)
        if((1<<c)&b) k=max(dp[c]+1,k);
        for(c=0;c<=30;c++)
        if((1<<c)&b) dp[c]=max(dp[c],k);
        ans=max(ans,k);
    }
    printf("%d\n",ans);
    return 0;
}