洛谷题目传送门 疯狂%%%几个月前就秒了此题的Tyher巨佬 借着这题总结一下决策单调性优化DP吧。蒟蒻觉得用数形结合的思想能够轻松地理解它。 首先,题目要我们求所有的\(p_i\),那么把式子变一下 \[p_i\ge a_j-a_i...
洛谷题目传送门 用两种不一样的思路立体地理解斜率优化,你值得拥有。 题意分析 既然所有的土地都要买,那么我们可以考虑到,如果一块土地的宽和高(其实是蒟蒻把长方形立在了平面上)都比另一块要小,那么肯定是...
洛谷题目传送门 闲话 看完洛谷larryzhong巨佬的题解,蒟蒻一脸懵逼 如果哪年NOI(放心我这样的蒟蒻是去不了的)又来个决策单调性优化DP,那蒟蒻是不是会看都看不出来直接爆\(0\)?! 还是要想点办法,不失一般性...
题意: 给定长度为n的序列a,问有多少个子区间,满足该子区间的最大值和最小值的差值<k 数据范围:n<=1e5,0<=a(i)<=1e9,0<k<=1e9 解法: 设[l,r]的极差为p,那么[l+1,r]...