首页 > 代码库 > Bzoj4300 绝世好题

Bzoj4300 绝世好题

2024-08-20 15:58:50   220人阅读

 

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1325  Solved: 722

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


Source

By Oxer

 

 

刚开始被吓到了，想了想，原来是个类似LIS的DP。

f[j]表示序列最后一个数二进制第j位为1的序列长度。具体转移见代码

 1 /*By SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #define LL long long 8 using namespace std; 9 const int mxn=100010;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 int n;17 int f[32],a[mxn],b[32];18 int main(){19     n=read();20     int i,j;21     for(i=1;i<=n;i++)22         a[i]=read();23     b[0]=1;24     for(j=1;j<=30;j++)25         b[j]=(b[j-1]<<1);26     for(i=1;i<=n;i++){27         int tmp=0;28         for(j=0;j<31;j++)29             if(a[i]&b[j]) tmp=max(tmp,f[j]+1);30         for(j=0;j<31;j++)31             if(a[i]&b[j]) f[j]=max(f[j],tmp);32     }33     int ans=0;34     for(j=0;j<31;j++)ans=max(ans,f[j]);35     printf("%d\n",ans);36     return 0;37 }

 

Bzoj4300 绝世好题


联系
我们