DP的各种优化（动态规划，单调队列，决策单调性，斜率优化）

前缀和优化

当DP过程中需要反复从一个求和式转移的话，可以先把它预处理一下。运算一般都要满足可减性。

比较naive就不展开了。

题目

暂时没找

单调队列优化

前置技能：单调队列（经典的问题模型：洛谷P1886 滑动窗口）

用于优化形如\(f_i=\min/\max_{j=l_i}^{i-1}\{g_j\}+w_i\)，且满足\(l_i\le l_{i+1}\)的转移。

人话：对于序列中的每个点，从其左侧一段决策区间内的最值进行转移，且决策区间随着序列下标的增大也不断右移（就像窗口向右滑动）。

设\(j<k\)，容易发现如果\(g_j\)劣于\(g_k\)的话，那么当决策区间移动到\(k\)以后，\(j\)永远不会成为最优决策点，再也不会被转移了。

于是，我们只要维护一个队列，满足下标递增，决策性递减。我们需要当前的队首成为最优决策点，那么当队首第一次超出了区间范围（以后也就永远超出了）就把它出队。为了保证单调性，队尾新加入点之前，要先把队列中比它劣的点依次从队尾出队。

题目

【Sol.】洛谷P1776 宝物筛选_NOI导刊2010提高（02）（就是多重背包）

【Done】洛谷P2254 [NOI2005]瑰丽华尔兹

决策单调性

更新中～

题目

【Sol.】洛谷P1973 [NOI2011]Noi嘉年华

【Todo】BZOJ4709 [Jsoi2011]柠檬

【Todo】CF868F Yet Another Minimization Problem（vjudge）

斜率优化

更新中～

题目

【Todo】洛谷P4072 [SDOI2016]征途

【Todo】洛谷P2900 [USACO08MAR]土地征用Land Acquisition

【Todo】洛谷P4383 [八省联考2018]林克卡特树lct

DP的各种优化（动态规划，单调队列，决策单调性，斜率优化）

原文：https://www.cnblogs.com/flashhu/p/9480669.html