题目
Description
给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-1!=0(2<=i<=len)。
Input
输入文件共2行。 第一行包括一个整数n。 第二行包括n个整数，第i个整数表示ai。
Output
输出文件共一行。 包括一个整数，表示子序列bi的最长长度。
Sample Input
3
1 2 3
Sample Output
2
HINT
n<=100000,ai<=2*10^9
题解
$f_{i,j}$表示前$i$个数最后一个数第$j$位为$1$的最长长度，$a_i$第$j$位为$1$的时候进行转移
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e5+5;
int n,ans;
int a[MAX];
int f[31][MAX];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
int x=0;
for(int j=0;j<=30;++j)
{
f[j][i]=f[j][i-1];
if(a[i]&(1<<j)) x=max(x,f[j][i]+1);
}
for(int j=0;j<=30;++j)
if(a[i]&(1<<j)) f[j][i]=x;
ans=max(ans,x);
}
return printf("%d",ans),0;
}
