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

2

HINT

对于100%的数据，1<=n<=100000，ai<=10^9。

Sol

智商下线，一开始以为是b[i]&b[i]-1….
我们二进制一下，然后
f[i]表示b数列最后一位第i位为1的最长数列
然后就好做了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdio>
#define max(a,b) (a>b)?a:b
using namespace std;
int n,f[31],x;
int main(){
	freopen(""1.in"",""r"",stdin);
	freopen(""1.out"",""w"",stdout);
	scanf(""%d"",&n);
	for (int i=1;i<=n;i++){
		scanf(""%d"",&x);
		int tmp=0;
		for (int j=0;j<=30 && (1<<j)<=x;j++)
			if ((1&(x>>j))){
				tmp=max(f[j]+1,tmp);
			}
		for (int j=0;j<=30 && (1<<j)<=x;j++){
			if ((1&(x>>j))){
				f[j]=max(tmp,f[j]);
			}
		}
	}
	int ans=0;
	for (int i=0;i<=30;i++)
		ans=max(ans,f[i]);
	printf(""%d\n"",ans);
	return 0;
}