洛谷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;
}