PA 2019 Runda 1 Muzyka pop 题解

题目分析

这道题要求我们选择 $n$ 个严格递增的非负整数 $b_1 < b_2 < \dots < b_n \leq m$，使得 $\sum_{i=1}^n \text{popcount}(b_i) \cdot a_i$ 最大化。

关键约束：

• $b_i$ 必须严格递增且不超过 $m$
• 目标函数与每个数的二进制表示中 1 的个数有关
• $m$ 可以非常大（最大 $10^{18}$），因此不能直接枚举

解题思路

核心观察

1. 数位DP思想：由于 $m$ 很大，我们需要按位考虑
2. 区间划分：在二进制表示中，高位相同的数构成一个连续区间
3. 最优子结构：问题可以分解为在二进制表示的各个位上做决策

算法设计

代码使用了一种基于二进制位的区间DP方法：

状态定义

f[d][l][r][t] 表示：

• 当前考虑二进制第 d 位（从低位到高位）
• 考虑原序列中区间 $[l, r]$ 的 $a_i$
• t=0 表示当前区间对应的所有 $b_i$ 在第 d 位都为 0
• t=1 表示当前区间对应的 $b_i$ 在第 d 位可以自由选择（受 $m$ 的限制）

状态转移

1. 当前位不选1：

   f[d & 1][l][r][0] = f[(d & 1) ^ 1][l][r][0] + max(0ll, s[r] - s[l - 1]);
   

2. 根据 $m$ 的当前位决定：

   • 如果 $m$ 的当前位为 1，可以选择是否在这一位放 1
   • 如果 $m$ 的当前位为 0，只能继续之前的状态

3. 区间分割： 将 $[l, r]$ 分割为 $[l, p]$ 和 $[p+1, r]$，分别处理高位和低位

代码详解

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int inf = 1e18;
int n, m, s[205], f[2][205][205][2];

signed main() {
    scanf("%lld%lld", &n, &m);
    
    // 预处理前缀和
    for (int i = 1; i <= n; i++)
        scanf("%lld", &s[i]), s[i] += s[i - 1];
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            f[1][i][j][0] = f[1][i][j][1] = -inf;
    }
    for (int i = 1; i <= n; i++)
        f[1][i][i][0] = f[1][i][i][1] = 0;
    
    // 按位DP，最多64位（因为 m <= 1e18 < 2^60）
    for (int d = 0; d <= 63; d++) {
        // 清空当前层
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                f[d & 1][i][j][0] = f[d & 1][i][j][1] = -inf;
        }
        
        // 处理所有区间
        for (int i = 1; i <= n; i++) {
            for (int l = 1, r = i; r <= n; l++, r++) {
                // 情况1：当前位为0
                f[d & 1][l][r][0] = f[(d & 1) ^ 1][l][r][0] + max(0ll, s[r] - s[l - 1]);
                
                // 情况2：根据m的当前位决定
                if ((m >> d) & 1)
                    f[d & 1][l][r][1] = max(f[(d & 1) ^ 1][l][r][0], 
                                           f[(d & 1) ^ 1][l][r][1] + s[r] - s[l - 1]);
                else
                    f[d & 1][l][r][1] = f[(d & 1) ^ 1][l][r][1];
                
                // 情况3：分割区间
                for (int p = l; p < r; p++) {
                    f[d & 1][l][r][0] = max(f[d & 1][l][r][0],
                        f[(d & 1) ^ 1][l][p][0] + f[(d & 1) ^ 1][p + 1][r][0] + s[r] - s[p]);
                    
                    if ((m >> d) & 1)
                        f[d & 1][l][r][1] = max(f[d & 1][l][r][1],
                            f[(d & 1) ^ 1][l][p][0] + f[(d & 1) ^ 1][p + 1][r][1] + s[r] - s[p]);
                }
            }
        }
    }
    
    printf("%lld", f[0][1][n][1]);
    return 0;
}

关键点解释

1. 前缀和的作用

s[i] 存储 $a_i$ 的前缀和，用于快速计算区间和，在状态转移中：

• s[r] - s[l-1] 表示区间 $[l, r]$ 的 $a_i$ 之和
• 当我们在某一位放 1 时，这一位会对区间内所有数贡献 1 的 popcount

2. 状态转移的含义

• 不选当前位：所有数在这一位都是 0，popcount 不增加
• 根据 $m$ 选择：如果 $m$ 的当前位是 1，我们可以选择在这一位放 1 或 0
• 区间分割：将数列分成两部分，分别对应高位和低位不同的选择

3. 滚动数组优化

使用 d & 1 实现滚动数组，将空间复杂度从 $O(64 \times n^3)$ 降到 $O(n^3)$

样例分析

样例1

输入: 3 5
       2 -1 3
输出: 9

最优解：$b_1=3$ (popcount=2), $b_2=4$ (popcount=1), $b_3=5$ (popcount=2) 计算：$2×2 + (-1)×1 + 3×2 = 9$

样例2

输入: 3 2
       1 1 -1
输出: 0

由于 $m=2$ 很小，最优解是选择 $b_1=0, b_2=1, b_3=2$ 等，但因为有负数，可能选择不取某些数。

复杂度分析

• 时间复杂度：$O(64 \times n^3)$，其中 64 是位数，$n=200$ 时可行
• 空间复杂度：$O(n^3)$，使用滚动数组优化

总结

这道题结合了数位DP和区间DP的思想，巧妙地解决了在巨大范围 $m$ 下的最优选择问题。算法的核心在于：

1. 按位处理：将大范围问题分解为各个二进制位的子问题
2. 区间划分：将数列分段处理，对应不同的二进制选择
3. 状态压缩：通过滚动数组优化空间

这种解法充分利用了二进制表示的性质，是处理大范围数位相关问题的典型方法。