题目内容

曾经有一个小镇，那里有一位叫做塔子哥的年轻人。他拥有一种非常特别的技能，能够通过操作数组来获得最大的收益。

塔子哥的技能最初得到了村里的某位老者的传授。老者告诉他，每次操作可以删除一个数 $arr_i$ ，同时删除所有等于 $arr_i+ 1$ 或者 $arr_i - 1$的数。操作后被删除的数无法再被选中。每次操作可以获得被删除数的分数，现在他想知道通过多次操作，他最多能够获得多少分。

为了帮助塔子哥，老者给了他一个长度为 $n$ 的数组 $arr$，并告诉他最优的操作策略是什么。现在，塔子哥需要你的帮助来解决这个问题。

题目思路

直接使用动态规划解决，$dp[0][i]$ 代表只考虑不大于i的数并且没有操作等于i的数时得到的最高得分，$dp[1][i]$ 代表只考虑不大于i的数并且操作了所有等于i的数时得到的最高得分，因为操作了 $i$ 就要删除所有等于 $i+1$的数，所以转移方程：

$dp[0][i] = max(dp[0][i-1], dp[1][i-1])$ $dp[1][i] = dp[0][i-1] + i*cnt[i]$

代码

Python代码