前言

对于最小化问题，二元转移函数 $w(i,j)$ 满足

也就是转移交叉优于转移包含，也就是决策单调性。

性质

四边形不等式是二维差分非正。

满足四边形不等式的矩阵，行最小值单调递增。

模型

最短路型dp

其中这个邻接矩阵满足四边形不等式。

做法是，决策单调性，考虑每一个 $j$ 能更新到哪里。

每个 $f(j)$ 可以转移一个后缀的 $f(i)$，你开一个栈，如果我栈顶的元素转移比我当前的要严格劣，那就弹栈，不然我入栈。判断是否严格劣使用二分，二分一个位置看谁更优来找到分割点。

k点最短路型dp

有两个性质，一个是决策单调性，一个是 $f(k,n)$ 关于 $k$ 具有下凸性，也就是你每增加一个点它优化的力度会减小，劣化的力度会增大。

所以如果你想求 $f(k,n)$，我们二分一个斜率切这个凸壳，那么你这样切实际上过了点 $(k,f(k,n))$，解出来斜率 $b=f-ks$，所以你实际上是在最小化这个 $b$，因为你是在从下往上切，因此你只需要二分斜率 $s$，给每个点一个附加值 $s$，你就可以得到当前选择的点数，然后你只需要二分到 $k$ 就行了。

这个玩意叫wqs二分。

区间型dp

$w$ 满足四边形不等式，并且还需要满足包含单调性（小的小于大的）

决策关于 $i,j$ 分别具有决策单调性，因为你固定某一个，另外一个就是上面那个东西。

令 $f(i,j)$ 决策点为 $S(i,j)$

分别固定 $i,j$ 有 $S(i,j-1)\le S(i,j)\le S(i,j+1)$

然后你考虑总共会考虑的转移点个数，一条折线下去是 $O(n)$ 的，总共有 $O(n)$ 条折线，因此是 $O(n^2)$ 的。

ZJOI2010 基站选址

这个东西是个 $k$ 步最短路。

$f(i,j)$ 表示我第 $i$ 个基站是 $j$ 的时候 $[1,j]$ 的费用。

转移的时候我们需要考虑 $[k,j]$ 的贡献，我们判断它是否具有四边形不等式。

考虑扰动，我们令 $j\to j-1$，考虑这个右端点移动会使得 $w$ 减少，再考虑 $k\to k+1$，那么你是不是就更少了，于是你得到交叉优于包含。

$f$ 关于 $i$ 是凸的，所以我们直接二分斜率可以干掉一维。

注意到 $w$ 是二维数点，并且边界递增，因此我们可以直接线段树维护，类似一个扫描线。

FJOI2020 物流仓库选址

数轴上选 $p$ 个点建仓库，每个点到最近仓库的距离乘上 $a_i$ 贡献费用，建仓库有 $c_i$ 代价，求最小总花费。

$f(i,j)=\min{k<j}f(i-1,k)+\sum{p=k}^ja_p\min{x_p-x_k,x_j-x_p}+c_j$

转移函数满足四边形不等式，所以我们二分斜率。

$g(i)$ 表示 $i$ 是仓库前提下 $1\to i$ 的最小费用。

$h(i)$ 表示 $i$ 对应的仓库在左边前提下 $1\to i$ 的最小费用。

$g,h$ 这两个互相转移，维护前缀和都可以斜率优化。

$h(i)=\min g(j)+\sum_p a_p(x_p-x_j)$

$g(i)=\min h(j)+\sum_{p>j}a_p(x_i-x_p)$

IOI2014 假期

考虑活动范围是怎样的，应该是 $s$ 往左 $l$ 往右 $r$。

移动的用时是 $l+r+\min(l,r)$。

不妨令 $l<r$，

那么你的得分就是 $[s-l,s+r]$ 区间当中较大的 $d-2l-r$ 个数的和。

决策确定 $r$，$l$ 满足决策单调性。

一个区间的得分可以用主席树干掉，于是你就可以考虑区间中点的决策来解决这个问题。

CTT2018 （wait）

$n$ 个点的树，以 $s$ 为根，把编号区间分成 $k$ 段，一个区间的得分是从 $s$ 出发经过所有点的最短回路的边数，求 $k$ 个区间的得分和的最大值。

维护每个 $j’$ 的转移。

利用 LCT access 过程当中均摊 $\log n$ 段不同贡献，用线段树维护一下。

解法2：

注意到满足四边形不等式。

考虑分治维护决策。

我们跑一个莫队，发现

左右端点的移动是 $O(n\log n)$ 的。

折线维护

APIO2016 烟花表演

令 $f(u,x)$ 表示修改 $u$ 的子树使高度为 $x$。

注意到这个玩意是关于 $x$ 下凸的，这个可以归纳证明。

考虑把 $v$ 合并到 $u$ 上的时候，对于每个 $i$ 的不同位置分别考虑贡献。

具体做起来比较麻烦，有点掉线。

ARC070E NarrowRectangles

草，没看题，寄了。

大概就是说，

这个东西是下凸分段一次函数。

你发现这个转移相当于左折线左移，右折线右移，然后加一个绝对值函数。

用两个堆维护左右折线然后打标记。

绝对值函数只有两个拐点，直接暴力挪就能维护平底在哪里了。

老鼠进洞

$n$ 个球 $m$ 个洞，每次将一个球放进一个洞，一个洞只能容纳一个球。

求最小总距离。

这题有 1145141919810 种做法。

$f(i,j)$ 表示前 $i$ 个点，求比洞多了 $j$ 个的最小路费。

对于球有 $f(i,j)=f(i-1,j-1)+|j|(x_{i+1}-x_i)$

对于洞有 $f(i,j)=\min{f(i-1,j),f(i-1,j+1)+|j|(x_{i+1}-x_i)}$

这个玩意学名叫线头dp，就是我们把匹配的贡献拆到边上，然后记录一个我钦定接下来会有几个与我当前的这些进行匹配。

之前 qyc 给我看过一个题感觉也有类似的思路，但是和这个没啥关系。

你发现它又是一个下凸的折线，支持平移取min，加绝对值。

还有就是模拟费用流。

一个球滚到左边的洞，代价 $a-b$。

一个球返回到 $b’$，代价是 $b’-a-(a-b)=b’-(2a-b)$，相当于把这个球关于这个洞对称一下然后继续走。

洞可以从前面挖走一个球，代价 $b-a$。

返回类似的，相当于一个 $2b-a$ 的洞。

于是我们用两个大根堆维护。

还有还有。

球的路径是没有交叉的，只有包含关系，并且一段区间的球一定是同方向的。

令 $f(i)$ 表示前 $i$ 个点没有出入的费用。

$j$ 是满足 $(x_j,x_i]$ 中球和洞相等的最大的 $j$。

$f(i)=f(j)+w(i,j)$

$f(i)=\min f(i-1),f(j)+w(i,j)$

其中 $w(i,j)$ 可以用前缀和算出来。

$j$ 可以双指针简单维护。

没有出处 CF573E Bear & Bowling

$n$ 个物品权值 $ai,b_i$，选一个物品序列 $i_1,\dots i_k$ 使得 $\sum{j=1}^k ((j-1)a{i_j}+b{i_j})$ 最大。

对于每个 $k$ 求最大值。

$n\le 3\times 10^5$

先把 $a_i$ 排序。

一个物品进到最优解就出不来了，不然你一定有更优的可以换掉它。

offline。

久违的计数题

求有多少长度为 $n$ 的由不超过 $m$ 的整数构成的序列 $a$ 使得 $ai\not | a{i+1}$，模数不一定是质数。

$n\le 3\times 10^5,m\le 10^5, Q\le 10^9$

$f(i,j)=\sum{k\not |j,k\le m}f(i-1,k)=\sum{1\le k\le m}f(i-1,k)-\sum_{k|j}f(i-1,k)$

发现任意排列素数因子，得到的转移方程是同构的。

把素因子降序排列后相同的可以算作同一种状态，不超过 $160$ 个。

快乐矩阵快速幂。

Mujin Programming Chanllenge 2018 日语题 タイル張り

用 $1\times 2$ 骨牌覆盖 $H\times W$ 棋盘，不能重叠或者超出。

两个方案不同当且仅当骨牌覆盖的格子集合不同。

$H\le 5,W\le 10^9,2s,1GB$

显然矩阵快速幂

你可以维护一个类似于插头的东西，一共 $32$ 个，但是有可能算重。

$f(i,S)$ 表示有可能伸出哪几种情况的插头。

搜一下发现 $S$ 从 $2^{32}\to 91$。