题解 P4310 【绝世好题】
swiftc
2019-06-28 20:37:25
我们设now[x]为前一个数二进制位第x位为1时的最大值
因为只有两个数有一个二进制为同为1时他们才可以连接，所以我们扫描每一个数，如果它二进制为第i位为1，找出这样最大的now[i]设为MAX，然后把每一个now[i]都设为MAX+1（把这个数接到前面最长的子序列上，让后边继续接）
### CODE：
```cpp
#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);
}
```