首页 > 代码库 > [bzoj4300][绝世好题] (动规)

[bzoj4300][绝世好题] (动规)

2024-09-01 16:58:12   217人阅读

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

Solution

什么gui

 

#include <stdio.h>#include <string.h>#define MaxBuf 1<<22#define RG register#define inline __inline__ __attribute__((always_inline))#define Blue() ((S==T&&(T=(S=B)+fread(B,1,MaxBuf,stdin),S==T))?0:*S++)#define dmax(a,b) ((a)>(b)?(a):(b))char B[MaxBuf],*S=B,*T=B;inline void Rin(RG int &x) {  x=0;RG int c=Blue(),f=1;  for(; c<48||c>57; c=Blue())    if(c==45)f=-1;  for(; c>47&&c<58; c=Blue())    x=(x<<1)+(x<<3)+c-48;  x*=f; }int n,x,ans,f[31];int main() {  Rin(n);  while(n--) {    register int t=0;    Rin(x);    for(register int i=0; i<=30; i++)      if(x&(1<<i))    t=dmax(f[i]+1,t);    for(register int i=0; i<=30; i++)      if(x&(1<<i))    f[i]=t;    ans=dmax(ans,t); }  printf("%d\n",ans);  fclose(stdin);  return 0; }

 

[bzoj4300][绝世好题] (动规)


联系
我们