我发现我根本不会 dp,然后我找点题做
CF1859D *1800
离散化,设 \(r_i\) 表示 \(i\) 的原值,dp 一个 \(f_i\) 表示在区间 \([r_i,r_{i+1})\) 起始的答案。
容易发现,我们向后跳是一定不优的,设当前在 \(p\),如果要向后跳那么一定是为了之后的向前跳到一个新的位置 \(r>p\),然而我们发现这样的话 \(p\) 也一定包含在 \(r\) 的大区间里面,这样就无需向后跳了。
类似的证明可以发现一定是跳到 \(b_i\) 上,因此从右往左扫,维护当前所有能跳到的 \(b_i\),选取最大的一个用 \(f_{b_i}\) 更新 \(f\),可以用 multiset
实现,时间复杂度 \(O(n\log n)\)。
CF1859E *2500
拆绝对值
标签:发现,区间,点题,一定,妹子,dp From: https://www.cnblogs.com/yukari1735/p/17648331.html