题解 P4310 【绝世好题】

· · 题解

\Large\texttt{My Blog}

题目链接：BZOJ 4300

给定一个长度为 n 的数列 a_i，求 a_i 的子序列 b_i 的最长长度 len，满足 b_i\ \texttt{AND}\ b_{i-1}\neq 0（2\leqslant i\leqslant len）。

数据范围：n\leqslant 10^5，a_i\leqslant 2\times 10^9

Solution

我们可以设计出一个不朴素的 \texttt{DP} 状态 f[i] 表示考虑前 i 个数的最长长度，转移为 f[i]=\max\{f[j]+1\}（a_i\ \texttt{AND}\ a_j\neq 0）。

考虑优化，发现这个东西和 \texttt{LIS} 非常类似。由于 a\ \texttt{AND}\ b\neq 0 意味着一定有一位为 1，所以我们用 f[i] 表示第 i 位为 1 的最长长度。每次读入一个 x，我们记 s=\max\{f[i]\}+1（x 的第 i 位为 1），然后用 s 去更新 f[i]，最后的答案即为 \max\{f[i]\}。

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

Code

#include <cstdio>
#include <algorithm>

const int N=35;
int n,f[N];

int main() {
    scanf("%d",&n);
    for(int x;n--;) {
        scanf("%d",&x);
        int mx=1;
        for(int i=0;i<=30;++i) if(x&(1<<i)) mx=std::max(mx,f[i]+1);
        for(int i=0;i<=30;++i) if(x&(1<<i)) f[i]=std::max(f[i],mx);
    }
    int ans=0;
    for(int i=0;i<=30;++i) ans=std::max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}