Bzoj4300 绝世好题

Posted by yjjr's blog on February 6, 2018

标签:DP,递推

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

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

 

分析:真是绝世好题……

第一眼看题秒出O(n^2)的算法,然后一直想着如何去优化成O(n log n)(模仿LIS优化那种)

乱七八糟想了一会儿,发现这是位运算,每个位之间是相互独立的

于是可以按位DP

F[i]表示第i位是1的子序列最长长度

转移:f[j]=max(f[k]+1) (1<<j)&x!=0 且(1<<k&x!=0

 

Code

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
LL n,mx,x,ans=0,f[35];
int main()
{
	n=read();
	rep(i,1,n){
		x=read();
		mx=0;
		rep(j,0,30)
		    if((1<<j)&x)mx=max(mx,f[j]);
		rep(j,0,30)
			if((1<<j)&x)f[j]=max(f[j],mx+1);
	}
	rep(i,0,30)ans=max(ans,f[i]);
	cout<<ans<<endl;
	return 0;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr