Description：

给定一个长度为 $n$ 的数列 $a_i$ ，求 $a_i$ 的子序列 $b_i$ 的最长长度，满足 $b_i\&b_{i-1}\ne 0$ 。

$1\le n \le100000$

Solution：

发现只要两个数有一位都是一就符合条件，于是设计状态为 $f[i]$ 表示到当前为止第 $i$ 位为一的最长长度，那么对于当前这个数，如果第 $k$ 位为 $1$ ，那么就可以从 $f[k]$ 转移过来，也可以转移到 $f[k]$ ，于是记录一个最大值即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int f[31];

int n;

int main()

{

    scanf("%d",&n);

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

    {

        int t,cnt = 0;

        scanf("%d",&t);

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

        {

            if(t & (1 << k))cnt = max(cnt,f[k] + 1);

        }

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

        {

            if(t & (1 << k))f[k] = max(f[k],cnt);

        }

    }

    int ans = 0;

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

    {

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

    }

    cout << ans << endl;

    return 0;

}