求k次二进制最低置位清零操作后序列的最小和（含思路）

给定序列 $a_1, a_2, ..., a_n$，可执行 $k$ 次操作，每次操作规则如下：

1. 选择序列中任意一个数 $a_i$（$1 \leq i \leq n$）
2. 将 $a_i$ 二进制表示中最低的置位（即最低位的1）从1改为0

需计算经过 $k$ 次操作后，序列总和的最小值。

输入格式 #

• 第一行输入两个整数 $n, k$
• 第二行输入 $n$ 个正整数，代表序列元素

输出格式 #

输出一个整数，表示操作后的序列总和最小值

示例 #

示例1 #

输入：

2 1
8 7

输出：

7

说明：8的二进制为1000，7的二进制为111。对8执行操作后序列变为[0,7]，总和为7；对7执行操作后序列变为[8,6]，总和为14，故最小值为7。

示例2 #

输入：

2 2
9 6

输出：

6

说明：9的二进制为1001，两次操作可将两个1置为0，剩余6，总和为6。

原问题可转化为最大化k次操作所减去的数值总和，因为最终总和最小值 = 序列初始总和 - 最大减去值。

核心分析 #

对任意数 $x$，每次操作减去的是其当前二进制最低位的1对应的数值。例如 $x=6$（二进制110）：

• 第1次操作减去2（最低位1对应的值），剩余4
• 第2次操作减去4，剩余0
  因此对 $x=6$ 执行t次操作的总收益（减去的数值）为：
• t=1时，收益2；t=2时，收益6

这完全符合分组背包模型：

• 背包容量：k（最多执行k次操作）
• 物品组：每个序列元素对应一组物品
• 组内物品：对元素x，生成m个物品（m为x二进制中1的个数），第t个物品的体积为t（需要t次操作），价值为执行t次操作的总收益（即x减去操作t次后的剩余值）

动态规划实现 #

1. 定义dp[j]：使用j次操作时，能获得的最大收益
2. 初始化dp[0] = 0，其余dp[j]初始为0（初始无操作时收益为0）
3. 对每个元素对应的物品组，倒序遍历背包容量（从k到0，避免重复选择同一组的多个物品），对每个物品（t次操作，收益v），若j >= t，则更新dp[j] = max(dp[j], dp[j-t] + v)
4. 最终答案 = 序列初始总和 - dp[k]

n, k = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)

# 预处理每个数的操作次数与对应收益
groups = []
for num in a:
    gains = []
    current = num
    cnt = 0
    sum_gain = 0
    while current > 0:
        # 取最低位的1
        low_bit = current & -current
        sum_gain += low_bit
        cnt += 1
        gains.append((cnt, sum_gain))
        current -= low_bit
    groups.append(gains)

# 分组背包DP
dp = [0] * (k + 1)
for group in groups:
    # 倒序遍历容量，避免重复选同一组的物品
    for j in range(k, -1, -1):
        for t, v in group:
            if j >= t:
                dp[j] = max(dp[j], dp[j - t] + v)

print(total - dp[k])

内容的提问来源于stack exchange，提问作者terran roger