「BZOJ 4300」绝世好题

发表于 | | 阅读次数:
字数统计: 318 字

Description

题目链接：BZOJ 4300

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

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

Solution

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

考虑优化，发现这个东西和 $\text{LIS}$ 非常类似。由于 $a\ \text{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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
}
0%