BZOJ 4300 绝世好题

4300: 绝世好题

Description

给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-!=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题，但转移并不像你所想的那样生猛。

　　如果我们用图的方式去思考它，就会发现很多神奇的东西。因为DP满足拓扑序，事情按着顺序来，所以很多时候都能这样思考。对于此题，因为bit<30，所以O（nlogai）绰绰有余。

status before		the number we consider	+1	status after
f(0)	-->	1	-->	f(0)
f(1)		0		f(1)
f(2)	-->	1	-->	f(2)

　　最后说一句，如果去掉前导0，那么速度将会快上很多很多……

　　亲测：112ms--〉80ms

 1 /**************************************************************
 2     Problem: 4300
 3     User: Doggu
 4     Language: C++
 5     Result: Accepted
 6     Time:92 ms
 7     Memory:1212 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 const int N = 100010;
12 int n, f[N], ans;
13 inline int max(int a,int b) {return a>b?a:b;}
14 int main() {
15     scanf("%d",&n);
16     for( int x,temp,i = 1; i <= n; i++ ) {
17         scanf("%d",&x);
18         temp=0;for( int j = 0; j <= 30; j++ ) if((x>>j)&1) temp=max(temp,f[j]);
19         temp++;for( int j = 0; j <= 30; j++ ) if((x>>j)&1) f[j]=max(f[j],temp);
20     }
21     for( int j = 0; j <= 30; j++ ) ans=max(ans,f[j]);
22     printf("%d
",ans);
23     return 0;
24 }

DP（位运算）