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

2

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

 

/**************************************************************
    Problem: 4300
    User: Doggu
    Language: C++
    Result: Accepted
    Time:92 ms
    Memory:1212 kb
****************************************************************/
 
#include <cstdio>
const int N = 100010;
int n, f[N], ans;
inline int max(int a,int b) {return a>b?a:b;}
int main() {
    scanf("%d",&n);
    for( int x,temp,i = 1; i <= n; i++ ) {
        scanf("%d",&x);
        temp=0;for( int j = 0; j <= 30; j++ ) if((x>>j)&1) temp=max(temp,f[j]);
        temp++;for( int j = 0; j <= 30; j++ ) if((x>>j)&1) f[j]=max(f[j],temp);
    }
    for( int j = 0; j <= 30; j++ ) ans=max(ans,f[j]);
    printf("%d\n",ans);
    return 0;
}