2023.02.02

orz psj，orz pb orj csy

可惜这一天我在复习考试没看直播。

参考

psj 的 apio 讲课，《决策单调性与四边形不等式》

p_b_p_b 的学习笔记。

csy 的讲课

oiwiki

slope trick

决策单调性

将 dp 抽象一下，给定一个向量 \(f\) 和一个矩阵 \(A\)，考虑求出一个向量 \(g_i=\min_j(f_j+a_{i,j})\)。

如果一个矩阵 \(A\) 的第 \(i\) 行的最小值的位置 \(b_i\) 是单调不减的就是单调矩阵。如果一个矩阵所有的子矩阵都是单调矩阵就称 \(A\) 是完全单调矩阵。

四边形不等式 \(i\le j,x\le y\)，\(A_{i,x}+A_{j,y}\le A_{i,y}+A_{j,x}\)。如果 \(j=i+1,y=x+1\) 满足四边形不等式，则 \(A\) 满足四变形不等式。满足四边形不等式的矩阵是蒙日矩阵。蒙日矩阵每一行或每一列加上一个常数 \(C\) 单调性不变。

由于蒙日矩阵一定是完全单调矩阵，所以dp方程有决策单调性

一般做法分治，假设当前分治区间是 \([l,r]\) 答案区间是 \([x,y]\) 考虑求出第 \(mid=\frac{l+r}{2}\) 行的最小值的位置 \(p\)，那么 \([l,mid-1]\) 的答案只能在 \([x,p]\) 取到，同理 \([mid+1,r]\) 的答案只能在 \([p,y]\) 取到，递归即可。

一般做法二分栈，对于任意两列，左边的列在一段前缀最优，右边的列在一段后缀更优。所以我们可以求出当前列第一个不如下一列的位置，这个二分求出。

NOI2009 诗人小G

直接列出转移方程 \(dp_i=length(j,i)^p+dp_j\)，这个幂函数显然是凸的于是它有决策单调性于是直接二分栈即可。

loj6039 雅礼集训2017 Day5 珠宝

把 \(C\) 相同的物品分成一组，肯定是从大到小选，记方程 \(f_{i,j}\) 代表前 \(i\) 组选则总体积为 \(j\) 个的最大收益，转移可以写成 \(f_{i,j}=\max f_{i-1,k}+s_{i,\frac{j-k}{i}}\)。其中 \(s_{i,{j-k}{i}}\) 是前缀和。

那这个 \(s_{i,\frac{j-k}{i}}\) 是单调的所以显然有决策单调性，按照模 \(i\) 个余数分类，然后直接分治即可。

CTT2018 ZYB的游览计划

分治做法的优势，在于如果矩阵元素不能 \(O(1)\) 计算的时候，如果可以快速扩展，用分治法类似莫队算法加入删除复杂度不变。而这一题只需要维护集合内的点的dfs序的顺序即可。

CF868F

和上一题近乎一样的做法