给定一个长度为$n\le10^6$的序列$x$。
你需要从序列中选出一些位置。对于第$i$个位置,如果它被选中,你会获得$x_i$的收益;如果它没被选中,找到最小的$j$使得第$j$个位置到第$i$个位置都没有被选中,你需要付出$i−j+1$的代价。
此外,你选出的位置必须满足$x_i$是单调不下降的。
最大化收益减去代价的结果。
昨天晚上肝了几道斜率优化的题,这里一起把题解写了吧。
CraZYali
MY WARM BLOG
DATA DELETED
文章
58
分类
6
标签
38
杂项
题解
题解 / 口胡
Update your browser to view this website correctly. Update my browser now
×