标签：DP，递推
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
分析：真是绝世好题……
第一眼看题秒出O(n^2)的算法，然后一直想着如何去优化成O(n log n)（模仿LIS优化那种）
乱七八糟想了一会儿，发现这是位运算，每个位之间是相互独立的
于是可以按位DP
F[i]表示第i位是1的子序列最长长度
转移：f[j]=max(f[k]+1) (1<<j)&x!=0 且（1<<k）&x!=0
Code
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
inline LL read()
{
LL f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
LL n,mx,x,ans=0,f[35];
int main()
{
n=read();
rep(i,1,n){
x=read();
mx=0;
rep(j,0,30)
if((1<<j)&x)mx=max(mx,f[j]);
rep(j,0,30)
if((1<<j)&x)f[j]=max(f[j],mx+1);
}
rep(i,0,30)ans=max(ans,f[i]);
cout<<ans<<endl;
return 0;
}
