给定一个序列，求满足 (Aleqmax-minleq B) 的最长的子序列
(nleq10^6)
维护递增递减两个单调队列，若两队首之差大于 (B) ，挪动较小左端点，并更新答案左端点
时间复杂度 (O(n))
poj1180 [IOI2002]Batch Scheduling
有 (n) 个任务，每个任务有时间 (T_i) 与花费 (F_i) 。将这些任务分组，每组花费为 (()之前花费的时间(+S+displaystylesum T_i) imes (sum F_i))
(nleq10^4, Sleq50, 1leq T_i, F_ileq100)
首先可以设计出一个状态数为 (n^2) 时间复杂度为 (O(n^3)) 的dp，用斜率优化可以做到 (O(n^2))
但这样空间会炸，考虑设计一个状态线性的dp
由于总时间 (=k imes S+displaystylesum_{i=1}^nT_i) 。将一段区间分为一组会使得剩下的所有数的时间增加 (S) ，也就使得剩下的花费增加了 (S imes displaystylesum_{i=now+1}^nF_i)
于是可以设计一个倒序dp，令 (f_i) 为 (i) 到 (n) 的任务分为若干组的最小花费，则 $$f_i=displaystylemin_{j>i}{f_j+(S+displaystylesum_{k=i}{j-1}T_i) imes(sum_{k=i}nF_i)}$$
可以斜率优化
令 (T_i=displaystylesum_{j=i}^nT_i, F_i=sum_{j=i}^nF_i)
则 (f_j=F_iT_j+f_i-SF_i-T_iF_i)
时间复杂度 (O(n))
一共有 (n) 天，每天买入价为 (AP_i) ，卖出价为 (BP_i) ，最多买入 (AS_i) 股，最多卖出 (BS_i) 股。两次交易至少间隔 (W) 天，任何时候最多持有 (m) 股。初始资金数目无限，求 (n) 天之后能赚到多少钱。
(1leq Wleq n, mleq2000, 1leq AP_i, BP_i, AS_i, BS_ileq1000)
令 (f_{i, j}) 为第 (i) 天，持有 (j) 股最多赚钱数目
考虑其中第二个式子，将括号拆开，把 (j imes AP_i) 提出来得到 (displaystylemax_{j-AS_Ileq kleq j}{f_{i-W-1, k}+k imes AP_i}-j imes AP_i)
可以发现 (max) 中只有与 (k) 相关的项，于是可以用单调队列优化
注意初值设置
时间复杂度 (O(nm))