给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-1!=0(2<=i<=len)。
n<=100000,ai<=2*10^9
首先明确：&的运算规则是有$1$则$1$
所以两个数只要任意一位，有一个有$1$，那么&后的结果就不会是$0$
直接按这个思路去$dp$就可以了
因为是子序列，所以$dp$数组直接按位开就好了
#include <bits/stdc++.h> using namespace std ; #define N 100010 int n , ans ; int a[ N ] , f[ 40 ] ; int main() { scanf( "%d" , &n ) ; for( int i = 1 ; i <= n ; i ++ ) scanf( "%d" , &a[ i ] ) ; for( int i = 1 ; i <= n ; i ++ ) { int tmp = 0 ; for( int j = 0 ; j <= 30 ; j ++ ) { if( a[ i ] & ( 1 << j ) ) tmp = max( tmp , f[ j ] + 1 ) ; } for( int j = 0 ; j <= 30 ; j ++ ) { if( a[ i ] & ( 1 << j ) ) f[ j ] = tmp ; } ans = max( ans , tmp ) ; } printf( "%d\n" , ans ) ; }
原文：https://www.cnblogs.com/henry-1202/p/9736008.html