题解

思路

如果最终选择了数值 $x$，那么同样等于 $x$ 的元素之间不会互相删除，因此应把所有 $x$ 都选完， 总贡献为 $x\cdot c_x$，其中 $c_x$ 是 $x$ 的出现次数。另一方面，选择过 $x$ 后，数值 $x-1$ 与 $x+1$ 都不能再产生贡献。

于是原问题等价于：在数轴上选择若干个互不相邻的数值 $x$，使 $\sum x\cdot c_x$ 最大。这是带点权路径上的最大权独立集。

做法

令 $f_i$ 表示只考虑数值 $1,2,\ldots,i$ 时的最大得分。对数值 $i$ 有两种选择：

• 不选 $i$，得分为 $f_{i-1}$；
• 选 $i$，则不能选 $i-1$，得分为 $f_{i-2}+i\cdot c_i$。

因此

从小到大递推至最大输入值即可。答案可能达到 $10^{10}$，必须使用 64 位整数。

子任务说明

• 当 $n\le20$ 时，可以枚举选中的元素子集，拒绝其中存在数值相差 $1$ 的方案并取最大和， 时间复杂度为 $O(2^n n^2)$。
• 当任意两个不同输入值之差都不为 $1$ 时，不同数值之间不会互相删除，选择全部元素就是最优， 直接求和即可。
• 一般情形使用上述频次 DP。

正确性证明

先证明同一数值 $x$ 在最优方案中要么全选，要么全不选。选择一个 $x$ 只会删除数值为 $x-1$ 与 $x+1$ 的元素，不会删除其他 $x$；因此一旦选择了 $x$，继续选择剩余的所有 $x$ 只会增加得分而不会带来新的限制。

考虑递推到数值 $i$ 的任意最优方案。若方案不选 $i$，其得分至多为 $f_{i-1}$，且该值可达。 若方案选择 $i$，根据相邻冲突必不选择 $i-1$；其余选择完全落在 $1$ 到 $i-2$ 中，最优贡献 为 $f_{i-2}$，再加上全部数值 $i$ 的贡献 $i\cdot c_i$。两类方案覆盖所有可能性，取最大值得到 的恰是 $f_i$。由归纳法，最终状态就是全局最优答案。

复杂度

设值域上界为 $V=10^5$。时间复杂度为 $O(n+V)$，空间复杂度为 $O(V)$。