BZOJ4300_绝世好题_KEY

题目传送门

刚开始是看到这道题目还以为是序列连续的。

当然了，序列可以不连续。

设f[i]表示到第i位时的序列的最长长度。

取cnt=Max f[j]+1，然后转移回去使f[j]=cnt。

这是为了让下次转移时能最优。

可以对读入数组进行滚动。

code：

/**************************************************************
    Problem: 4300
    User: yekehe
    Language: C++
    Result: Accepted
    Time:52 ms
    Memory:920 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int MAXN=35;
 
char tc()
{
    static char tr[100000],*A=tr,*B=tr;
    return A==B&&(B=(A=tr)+fread(tr,1,100000,stdin),A==B)?EOF:*A++;
}
 
int read()
{
    char c;while(c=tc(),c!='-'&&(c<'0'||c>'9'));
    int x=0,y=1;c=='-'?y=-1:x=c-'0';
    while(c=tc(),c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0';
    return x*y;
     
}
 
int N,a,w[MAXN],ans,cnt;
 
int main()
{
    N=read();
    register int i,j;
        for(i=1;i<=N;i++){
            cnt=0;a=read();
            　　for(j=0;j<31;j++)if(a&(1<<j))cnt=max(cnt,w[j]+1); 
            　　for(j=0;j<31;j++)if(a&(1<<j))w[j]=cnt;
            ans=max(ans,cnt);
        }
    printf("%d",ans);
    return 0;
}