简述

　　我好像绕了一个大弯然后才绕到正解上。 　　 O(n2) 的做法是显然的，考虑 cdq 分治，每次处理左边对右边的影响，考虑怎样就能转移？ 　　题目要求是 bitand 结果不为 0 ，也就是有公共的某一位等于1，因为现在我们不考虑顺序，于是想到这样一种方法：枚举当前数字的每一个等于 1 的位，看看前面哪个数这位上也是1，然后转移；发现这个过程可以用桶优化，就是开个有 30 个元素的桶， w[i] 表示第 i 位等于1的数的 dp 最大值，扫描一遍前半区间，更新下这个桶就好。对于后面每个数，可以用桶来转移。 　　这样是 O(nlog2n) 的，再仔细一想，其实不用 cdq 分治也能做，直接把这个序列扫一遍，做同样的事情不就好了

代码

//dp #include <cstdio> #include <algorithm> #define maxn 100010 using namespace std; int w[40], ans, N; int main() { int i, x, j, f, t; scanf("%d",&N); for(i=1;i<=N;i++) { scanf("%d",&x); for(j=0,f=0,t=x;j<=30;j++,t>>=1)if(t&1)f=max(f,w[j]); f++; for(j=0,t=x;j<=30;j++,t>>=1)if(t&1)w[j]=max(w[j],f); } for(i=0;i<=30;i++)ans=max(ans,w[i]); printf("%d",ans); return 0; }