P1792 极简题解

· · 个人记录

做法

基础贪心：用优先队列维护值最大的点，选了一个点之后将其退出优先队列
改进：由于选一个点周围两个点可能比选了这个点更优，所以建立一个新的点，代表选了这两个点的收益（要减去选中间点的收益抵消影响）（权值：a_{mid-1}+a_{mid+1}-a_{mid}）

就是可反悔的贪心。

Code

正在写。