洛谷P4310 绝世好题 题解

题目链接：P4310 绝世好题

题意：给定一个长度为 $n$ 的数列 $a_i$ ，求 $a_i$ 的子序列 $b_i$ 的最长长度 $k$，满足 $b_i \& b_{i-1} \ne 0$，其中 $2\leq i\leq k$， $\&$ 表示位运算取与。

设 $dp[i][j]$ 为前 $i$ 个数的每个子序列的最后一个数第 $j$ 位为 $1$ 的最大长度

然后对于每个数枚举一遍dp，再转移一遍dp即可

注意到这个递推式可以滚动数组，然后搞一搞就好了

答案就是 $\max(dp[i][j])$

时间复杂度 $O(n \log \max(a_i))$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int n,res,dp[35];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,x; i<=n; i++)
    {
        cin >> x;
        int mx=1;
        for(int j=0; j<=33; j++)
            if((1<<j)&x)mx=max(mx,dp[j]+1);
        for(int j=0; j<=33; j++)
            if((1<<j)&x)dp[j]=max(dp[j],mx);
        res=max(res,mx);
    }
    cout << res << endl;
    return 0;
}