bzoj4300 绝世好题

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

HINT

n<=100000,ai<=2*10^9

正解：动态规划。

很简单的一道dp题。。设f[i]为做到当前位二进制位为i的最长子序列。然后直接转移就行了。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <complex>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <cstdio>
 8 #include <vector>
 9 #include <cmath>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #define inf (1<<30)
15 #define N (100010)
16 #define il inline
17 #define RG register
18 #define ll long long
19 
20 using namespace std;
21 
22 int f[35],a[N],n,res,ans;
23 
24 il int gi(){
25     RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
26     if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;
27 }
28 
29 il void work(){
30     n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi();
31     for (RG int i=1;i<=n;++i){
32     res=0; for (RG int j=0;j<=30;++j) if (a[i]&(1<<j)) res=max(res,f[j]);
33     res++; for (RG int j=0;j<=30;++j) if (a[i]&(1<<j)) f[j]=res;
34     }
35     for (RG int i=0;i<=30;++i) ans=max(ans,f[i]);
36     printf("%d
",ans); return;
37 }
38 
39 int main(){
40     work();
41     return 0;
42 }