swift's blog

swift's blog

题解 P4310 【绝世好题】

posted on 2019-06-28 20:37:25 | under 题解 |

我们设now[x]为前一个数二进制位第x位为1时的最大值

因为只有两个数有一个二进制为同为1时他们才可以连接,所以我们扫描每一个数,如果它二进制为第i位为1,找出这样最大的now[i]设为MAX,然后把每一个now[i]都设为MAX+1(把这个数接到前面最长的子序列上,让后边继续接)

CODE:

#ifdef DEBUG
#include"stdc++.h"
#else
#include<bits/stdc++.h>
#endif
using namespace std;
int main(){
    int n,a[100001],now[41],ans=-1;
    memset(now, 0, sizeof(now));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int maxn=-1;
        for(int j=0;j<=40;j++){
        //10^9<2^40,所以扫描1~40位即可
            if(a[i]&(1<<j)){//可以连接
                maxn=max(maxn,now[j]+1);
            }
        }
        for(int j=0;j<=40;j++){
            if(a[i]&(1<<j)){
                now[j]=maxn;
                //把这个数接到最长的子序列上
            }
        }
        ans=max(ans,maxn);
        //更新答案
    }
    printf("%d\n",ans);
}