题目描述

给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-1!=0(2<=i<=len)。

输入

输入文件共2行。

第一行包括一个整数n。

第二行包括n个整数，第i个整数表示ai。

输出

输出文件共一行。

包括一个整数，表示子序列bi的最长长度。

样例输入

3

1 2 3

样例输出

2

---

题解

dp

设f[i]为选i时前i个元素的最多个数。

那么就有f[i]=max{f[j]}+1 (a[j]&a[i]!=0)

这样会TLE，于是想优化。

如果a&b!=0，根据定义，a、b的二进制数中至少有一位都为1。

那么我们可以开一个辅助数组maxn[k]，记录一下所有a[i]中二进制第k位为1的f[i]的最大值。

然后扫一遍每个a[i]的数位，取最大值加到f[i]里并更新即可。

#include 
     
      #include 
      
       using namespace std;int a[100010] , f[100010] , maxn[32];int getnum(int n){	int i;	for(i = 0 ; i < 31 ; i ++ )		if((1 << i) == n)			return i;	return 0;}int main(){	int n , i , j , t , ans = 0;	scanf("%d" , &n);	for(i = 1 ; i <= n ; i ++ )		scanf("%d" , &a[i]);	for(i = 1 ; i <= n ; i ++ )	{		f[i] = 1;		for(j = a[i] ; j ; j -= j & (-j))			f[i] = max(f[i] , maxn[getnum(j & (-j))] + 1);		for(j = a[i] ; j ; j -= j & (-j))		{			t = getnum(j & (-j));			maxn[t] = max(maxn[t] , f[i]);		}		ans = max(ans , f[i]);	}	printf("%d\n" , ans);	return 0;}