给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-1!=0(2<=i<=len)。
n<=100000,ai<=2*10^9
这道题其实想到了就简单了，是一道根据位计算的DP题。
因为两个&为0的话，必须得所有位置都至少有一个为0
那么这一位，两个数都是1的话，就不会为0了
令f[i]表示第i位为1的最长长度，然后转移就好了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> using namespace std; int n,f[51]; int main() { scanf("%d",&n); memset(f,0,sizeof(f)); int i,j; int ans=0; for (i=1;i<=n;i++) { int x; scanf("%d",&x); int t=0; for (j=0;j<=30;j++) if (x&(1<<j)) t=max(t,f[j]+1); for (j=0;j<=30;j++) if (x&(1<<j)) f[j]=t; ans=max(ans,t); } printf("%d\n",ans); }
原文：http://www.cnblogs.com/hnqw1214/p/6476072.html