翻zky学长的blog时翻出来的.....

4300: 绝世好题

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 736 Solved: 393

[Submit][Status][Discuss]

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。

Source

By Oxer

记录每一位长度的最大值，每读一个数更新最大值即可

没想到这题这么蛋疼.....

附上代码:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int f[50];

int n;

int x;

int ans;

int tmp; 

int main()

{

    scanf("%d",&n);

    for (int i=1; i<=n; i++)

        {

            scanf("%d",&x);tmp=0;

            for (int j=0; j<=30; j++)

                if (x&(1<<j))

                    tmp=max(tmp,f[j]+1);

            for (int j=0; j<=30; j++)

                if (x&(1<<j))

                    f[j]=max(f[j],tmp);

        }

    for (int i=1; i<=30; i++)

        ans=max(ans,f[i]);

    printf("%d\n",ans);

    return 0;

}