题解 P4310 【绝世好题】
ShineEternal
2019-10-13 15:46:01
[如有残缺请点击这里](https://blog.csdn.net/kkkksc03/article/details/102533589)
## description：
$给定一个长度为n的数列ai，求ai的子序列bi的最长长 度len，满足b_i$ $and$ $b_{i−1} != 0(2 ≤ i ≤ len)$
$n ≤ 10^5$
$a_i ≤ 10^9$
## solution:
## code:
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
int dp[105];
int main()
{
int n;
scanf("%d",&n);
int a;
int ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
int k=1;
for(int j=0;j<=30;j++)
{
if((1<<j)&a)
{
k=max(dp[j]+1,k);
}
}
for(int j=0;j<=30;j++)
{
if((1<<j)&a)
{
dp[j]=max(dp[j],k);
}
}
ans=max(ans,k);
}
printf("%d\n",ans);
return 0;
}
```