BZOJ 4300: 绝世好题 二进制

对于每一个数字拆位，然后维护一个大小为 30 左右的桶即可.

code:

#include <bits/stdc++.h>

#define N 100006

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int mx[N];

int main() {

    // setIO("input");

    int i,j,n,ans=0;

    scanf("%d",&n);

    for(i=1;i<=n;++i) {

        int x,cur=0;

        scanf("%d",&x);

        for(j=0;1ll*(1ll<<j)<=1ll*x;++j)

            if(x&(1<<j)) {

                cur=max(cur,mx[j]+1);

            }

        for(j=0;1ll*(1ll<<j)<=1ll*x;++j)

            if(x&(1<<j))

                mx[j]=cur;

        ans=max(ans, cur);

    }

    printf("%d\n",ans);

    return 0;

}