Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
本题目属于 线性动态规划 + 互斥选择类问题。
这类问题的共性：
| 特征 | 描述 | |
|---|---|---|
| 值域冲突 / 相邻值不能共存 | 选了 x，就不能选 x-1 和 x+1 | |
| 可以预处理成权值数组 | 先统计每个值的总权重（value × count） | |
| 决策空间变成线性 | 在值域上做动态规划，而不是在原数组的下标上做 | |
| 状态转移模式固定 | dp[x] = max(dp[x - 1], dp[x - 2] + x * count[x]) |
Comments