如何证明Codeforces问题A. Boredom对应题解的正确性？

题目规则 #

给定由n个整数构成的序列a，玩家可执行多步操作。单步操作中玩家可选择序列内的一个元素（记为a_k）删除，此时序列中所有值等于a_k+1与a_k-1的元素也会被同步删除，该步操作将为玩家贡献a_k点得分。求玩家可获得的最高总得分。

参考代码 #

你看到的用户提交代码如下：

input()
z = [0] * 7**6
for i in map(int, input().split()):
    z[i] += i
a = b = 0
for i in z:
    a, b = max(a, i + b), a
print(a)

逻辑拆解 #

你已经理解了预处理部分的逻辑：
数组z的下标对应序列里可能出现的数值，z[x] = x * 序列中值为x的元素个数。这个预处理的依据很简单：如果你决定拿数值x的分数，那么所有x+1、x-1的元素都会被删除，剩下的所有x你可以全部拿走，总收益固定是z[x]，不存在只拿部分x的更优选择。

核心的循环部分本质是空间优化后的动态规划，对应经典的「打家劫舍」问题模型：

1. 先写无空间优化的DP状态定义：设dp[x]为处理完0到x所有数值时，能拿到的最高得分。
2. 对每个数值x，只有两种互斥的选择：
   • 不拿x的分数：此时x-1拿不拿都不受影响，最高得分就是处理完x-1的最优值dp[x-1]
   • 拿x的分数：此时x-1绝对不能拿，最高得分就是x的总收益加上处理完x-2的最优值z[x] + dp[x-2]
3. 因此状态转移方程为：dp[x] = max(dp[x-1], z[x] + dp[x-2])

代码里的两个变量就是用来压缩DP数组空间的：

• 遍历z数组时是从0开始从小到大逐个数处理的，进入当前轮（处理数值i）时：
  • 旧值a存储的是处理完i-1时的最优得分，也就是dp[i-1]
  • 旧值b存储的是处理完i-2时的最优得分，也就是dp[i-2]
• 执行a, b = max(a, i + b), a时：
  • 先算出当前i对应的最优值max(a, i + b)，作为新的a，供下一轮处理i+1时当dp[i]使用
  • 把旧的a（也就是dp[i-1]）赋值给新的b，供处理i+2时当dp[i]使用
• 遍历完所有数值后，a存储的就是处理完全部数值后的全局最优得分，直接输出即可。

补充说明：代码初始化z数组长度为7**6（即117649），是因为题目给定的序列元素最大值不超过1e5，这个长度足够覆盖所有可能出现的数值，不会出现下标越界问题。

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