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
解法： 因为两个&为0的话，必须得所有位置都至少有一个为0
那么这一位，两个数都是1的话，就不会为0了
令dp[i]表示第i位为1的最长长度，然后转移就好了。 代码：
//BZOJ 4300 #include <bits/stdc++.h> using namespace std; int n, dp[50], a[100010]; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); memset(dp, 0, sizeof(dp)); int ans = 0; for(int i = 1; i <= n; i++){ int cur = 0; for(int j = 0; j <= 30; j++){ if((a[i]>>j)&1){ cur = max(cur, dp[j]+1); } } for(int j = 0; j <= 30; j++){ if((a[i]>>j)&1) dp[j] = cur; } ans = max(ans, cur); } cout << ans << endl; }