如何证明Codeforces问题“A.Boredom”这个解决方案的正确性？

Question

我正在研究 Codeforces 问题 A。无聊：

给定一个由 𝑛 整数组成的序列 𝑎。玩家可以执行多个步骤。只需一步，他就可以选择序列中的一个元素（让我们将其表示为 𝑎_𝑘）并将其删除，此时所有等于 𝑎_𝑘+1 和 𝑎_𝑘−1 的元素也必须从序列中删除顺序。这一步会给玩家带来 𝑎_𝑘 积分。

我发现以下由用户 Leeisateam 提交的代码：

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

的列表

[0 X count_in_sequence(0),  1 X count_in_sequence(1), ..., n X count_in_sequence(n)].

之后，为

b

分配

a

的值，并且

a

在下一次迭代中使用该（先前的）值。我尝试过归纳法，但我仍然不明白为什么这段代码总是有效。

Answer 1

一些观察：

• 序列的顺序并不重要。如果你打乱输入顺序，输出仍然是相同的。所以我们不妨考虑对输入进行排序。
• 当值被“隔离”时，即数组不再具有少一或多一的值，那么我们应该始终接受它：没有“惩罚”——只有选定的值会从数组中删除。如果我们不接受它，那么在执行完所有其他可能的动作之后，它仍然会在那里，并且我们仍然会在游戏结束时接受它。
• 如果相同的值多次出现，并且我们决定采用其中一个，那么我们当然也应该采用其他出现的情况，因为这样我们就达到了前一点的情况：将不再有“附带损害”（如“相邻”值已被第一次选择删除）。
• 如果我们有一个包含 𝑛 数字的输入，其中所有唯一数字都在 1 到 𝑛 之间，并且 𝑛 为奇数，那么我们通过取 1, 3, 5,... 𝑛-2, 𝑛 来最大化。
• 如果我们有与上面相同的，但现在 𝑛 是偶数，我们会取 2, 4, 6, ..., 𝑛-2, 𝑛。我们也可以考虑 1, 3, 5,... 𝑛-3, 𝑛-1，或者在中间留一个额外的间隙（例如 1, 3, 6, 8, 10,... 𝑛-2, 𝑛），但最终第一个变体将具有最大总和。
• 当从左到右移动输入时，我们只需要考虑两种情况：第一种情况是选择了当前值减一，第二种情况是没有选择。在第二个场景中，我们可以选择当前值，在第一个场景中我们不能，因为它已被上一步移动删除。如果我们使用第二个场景选择当前值，它会自动成为下一个潜在移动的第一个场景（值加一），而第一个场景成为关于（值加一）的第二个场景。因此，我们选择不同的场景，并最终选择两者中最好的场景。

现在让我们看一下代码。

代码将值投影到相应的索引，以便自动按升序访问它们。

然后引入变量

a

和

b

。它们代表在采用（或不采用）当前值 

i 之前选择值的两种替代解决方案。由 a

 表示的值可能会取值 

i-1

，因此如果这样做，值 

i

 将不再可用（如上一个选择所删除的那样）。因此，我们不考虑选择 

a

 的 

i

 场景。另一方面，

b

代表了一个变体，我们肯定

没有

选择了

i-1，所以我们确信在场景b

之后我们也可以选择值

i

。所以现在

在考虑了

i

之后，我们有两种情况：a（未扩展）和

b + i

（另请注意，

i

总结了所有重复项，因为我们知道我们想要采取全部或全部）。在循环的下一次迭代中，

a

和

b

的角色发生变化，因为现在

b

可能选择了之前的

i

，现在是

i-1

，而之前的

b

现在是

a

（就像交换）。因此循环“交替”通过

z

数组，跟踪两种可能的情况。

用文字描述它会变得非常冗长，但它确实有助于使用一些有限的输入用一张纸单步执行代码。