Delete and Earn

给一个数组, 给一个操作: 删除一个数字, 然后得到这个数字的分数, 并且必须删除这个数字-1和+1的所有数字, 求最大的分数.

这题就是dp+贪心, 因为要得到最高的分数, 所以肯定要删大的先, 找到最大的删后, 就不用担心这个数字有+1的数字被删掉了. 然而只是贪心不够的, 因为如果是按照排序的数删除的话, 会有[10,8,8,8,8,8]这类情况, 所以还是要dp.

那么设dp[i]为删到大小为i的时候最大的分数. 那么dp[0] = 0, dp[1] = {all 1}, dp[2] = max{all 2 + dp[0], dp[1]}. dp[3] = max{all 3 + dp[1], dp[2]}

dp[i] = {dp[i-2] + sum[i], dp[i-1]}意义是: 两种选法儿, 第一种是选i-2的最佳答案,并且加上sum[i], 因为隔了一个, 所以是能选的. 第二种选法是选上一个的最佳答案, 这次的不要了