CSP-S 2020 第一轮 第43题：完善程序（第 20 题）第 3 空

题目

2.（最优子序列）取 $m = 16$，给出长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n(0 \le a_i < 2^m)$。对于一个二进制数 $x$，定义其分值 $w(x)$ 为 $x + \operatorname {popcnt}(x)$，其中 $\operatorname{popcnt}(x)$ 表示 $x$ 二进制表示中 $1$ 的个数。对于一个子序列  $b_1,b_2,\dots,b_k$，定义其子序列分值 $S$ 为 $w(b_1 \oplus b_2) + w(b_2 \oplus b_3) + w(b_3 \oplus b_4) + \cdots + w(b_{k-1} \oplus b_k)$。其中 $\oplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数 $n(1 \le n \le 40000)$ 接下来一行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

提示：考虑优化朴素的动态规划算法，将前 $\dfrac{m}{2}$ 位和后 $\dfrac{m}{2}$ 位分开计算。

Max[x][y] 表示当前的子序列下一个位置的高 $8$ 位是 $x$、最后一个位置的低 $8$ 位是 $y$ 时的最大价值。

试补全程序。

#include <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];

int w(int x)
{
    int s = x;
    while(x)
    {
        ①;
        s++;
    }
    return s;
}

void to_max(LL &x, LL y)
{
    if(x < y)
        x = y;
}

int main()
{
    int n;
    LL ans = 0;
    cin >> n;
    for(int x = 0; x <= MS; x++)
        for(int y = 0; y <= MS; y++)
            Max[x][y] = -INF;
    for(int i = 1; i <= n ; i++)
    {
        LL a;
        cin >> a;
        int x = ② , y = a & MS;
        LL v = ③;
        for(int z = 0; z < = MS; z++)
            to_max(v, ④);
        for(int z = 0; z < = MS; z++)
            ⑤;
        to_max(ans , v);
    }
    cout << ans << endl;
    return 0;
}

⑤处应填（ ）

选项

• A. to_max(Max[y][z], v + w(a ^ (z << B)))
• B. to_max(Max[z][y], v + w((x ^ z) << B))
• C. to_max(Max[z][y], v + w(a ^ (z << B)))
• D. to_max(Max[x][z], v + w(y ^ z))

答案

B

题解

选 B：

``cpp to_max(Max[z][y], v + w((x ^ z) << B)); ``

关键是理解：Max 提前算好了下一次转移中，高 8 位的贡献。

当前读入的数 a，高 8 位是 x，低 8 位是 y。计算完第一个循环后，v 表示以当前 a 结尾的子序列的最大分值。

接下来更新 Max：

• 枚举下一个数的高 8 位 z。
• 当前最后一个数是 a，其低 8 位是 y，所以更新 Max[z][y]。
• 当前数与下一个数的高 8 位异或结果是 x ^ z，放回原来的位权，需要左移 B 位，因此提前加上的贡献是 w((x ^ z) << B)。

于是更新式就是：

``cpp to_max(Max[z][y], v + w((x ^ z) << B)); ``

这里不能用 C 中的 w(a ^ (z << B))，因为它还包含当前数低 8 位 y 的贡献；下一次转移时，低 8 位应当与下一个数的低 8 位异或后再计算。