「洛谷 P4310」绝世好题 - 线性 DP + 位运算

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

给定一个长度为 \(n\) 的序列 \(a_{1 \cdots n}\)，求它满足 \(\forall i \in \left[ 1, n \right) , b_i \& b_{i + 1} \neq 0\) 的子序列 \(b\) 的最大长度，其中 \(\&\) 是按位与操作。

数据范围：\(1 \leq n \leq 1 \times 10^5\)，\(1 \leq a_i \leq 10^9\)

解题思路

显然我们可以使用线性 DP 解决这个问题。将遍历到的 a_i 的长度作为状态，很明显有下列转移方程：

\[ f_i = \max \limits_{1 \leq j < i \wedge a_i \& a_j \neq 0} \{ f_j + 1 \} \]

但这个算法时间复杂度为 \(O(n^2)\)，在实际测试中仅可获得 60 分。

接下来我们需要优化这个算法。显然在寻找满足 \(1 \leq j < i \bigwedge a_i \& a_j \neq 0\) 的数花的时间过长，我们可以对这进行优化。

我们可以从 \(a_i \& a_j \neq 0\) 下手。显然在 \(a_i\) 与 \(a_j\) 的二进制表示中必定含有一或以上的位数同时不为 \(0\)。我们可以通过维护一个数组 \(\text{bit}\)，在 \(\text{bit}_x\) 中记录所有在二进制下第 \(x\) 位不为 \(0\) 的 \(a_i\) 对应的 \(f_i\) 的最大值。利用该方法我们可以把上面的状态转移方程优化成下列样式：

\[ f_i = \max \limits_{0 \leq 2^j < a_i} \{ \text{bit}_j + 1 \} \]

在 \(f_i\) 计算完毕后更新 \(\text{bit}\) 数组即可。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cstring>
#include <iostream>

const int MAXN = 1e5;

int main() {
    int n;
    static int a[MAXN + 1];

    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    static int f[MAXN + 1], bit[31], ans = 0;
    memset(bit, 0, sizeof(bit));

    for (int i = 1; i <= n; i++) {
        f[i] = 1;

        for (int j = 0; (1ll << j) <= a[i]; j++) {
            if (((1 << j) & a[i]) != 0) {
                f[i] = std::max(f[i], bit[j] + 1);
            }
        }
        ans = std::max(ans, f[i]);
        for (int j = 0; (1ll << j) <= a[i]; j++) {
            if (((1 << j) & a[i]) != 0) {
                bit[j] = std::max(bit[j], f[i]);
            }
        }
    }

    std::cout << ans << std::endl;

    return 0;
}