DP优化

数据结构优化

单调队列优化

CF372C Watching Fireworks is Fun

简单DP题， 推柿子， 然后套单调队列。

SCOI2010 股票交易

可买可卖， 所以状态不能钦定买还是卖， 尽量让状态简单一点可以是优化更简单， 只是转移分讨更多， 设 \(f[i][j]\) 表示第 \(i\) 天结束时， 有 \(j\) 股票时的最大收益， 推式子套单调队列即可。

CSP-S2021划分

\(O(n^2)\) 是简单的， 考虑现在式子异常简单， 反而很难优化。 所以只能找一找神秘性质， 就是对于 \(i\) 的最优决策点 \(pre_j\) 一定是最靠近 \(i\) 的合法划分的点。 这样我们只需要找合法的划分即可， 在一个区间内最靠右的且满足有关于 \(sum\) 的不等式的点， 所以直接单调队列。

结论证明就不写了。