CSP-S 提高级 · CSP 2020 提高级第一轮 第 20 题

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_

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

看到折半优化 DP → 先拆高低 8 位独立算，再合并异或贡献。

popcnt 技巧易记混符号；高 8 位提取写成掩码只取第 8 位；v 初始误为-INF；转移时把 y^z 错成 a^z；DP 下标搞反且漏左移。

考点：折半优化 DP｜位运算 popcnt

程序在做什么

输入序列，维护 Max[x][y] 表示下一个高 8 位为 x、当前低 8 位为 y 的最大子序列分值。将 16 位拆为两个 8 位独立计算，最后合并。