四边形不等式
石子合并！
$f[i,j]=\max _ {i \le k < j} { f[i,k]+f[k+1,j]+w[i,j] }$
最优决策点？每一行单调并且每一列单调！
$p[i,j-1] \le p[i,j] \le p[i+1,j]$
四边形不等式：
$w[a,c]+w[b,d] \le w[a,d]+w[b,c] (a \le b \le c \le d)$
实际上是：
$w[b,d]-w[b,c] \le w[a,d]-w[a,c]$
区间包含关系单调？
$w[a,d] \ge w[b,c] (a \le b \le c \le d)$
有以下结论：
- 若 $w$ 满足四边形不等式，且区间包含关系单调，则 $f$ 也满足四边形不等式
- 若 $f$ 满足四边形不等式，则 $p[i,j-1] \le p[i][j] \le p[i+1][j]$
- $p$ 的每一行单调增且每一列单调增
- 由于填充满 $p$ 只需要 $O(n^2)$ 的时间，所以计算 $f$ 过程中的枚举总时间复杂度是 $O(n^2)$
- 若 $w$ 满足四边形不等式，当且仅当 $w[i,j] + w[i+1,j+1] \le w[i+1,j]+w[i,j+1]$
Part I
当 $w[i,j]+w[i+1,j+1] \le w[i+1,j]+w[i,j+1]$ 时，
即 $w[i,j]-w[i+1,j] \le w[i,j+1]-w[i+1,j+1]$
即 $(w_i-w_{i+1})(j) \le (w_i-w_{i+1})(j+1)$
所以 $w$ 相邻行差分后是单调的
所以 $\forall c \le d$，有 $(w_{i}-w_{i+1})(c) \le (w_{i}-w_{i+1})(d)$
同理，$\forall a \le b$，从 $(w_{a}-w_{a+1})$ 开始不断累加，得到 $(w_a-w_{b})$
于是有 $(w_{a}-w_{b})(c) \le (w_a-w_{b})(d)$
即 $w[a,c]+w[b,d] \le w[b,c]+w[a,d]$
Part II
之后证明 $f[i,j]+f[i+1,j+1] \le f[i,j+1]+f[i+1,j]$
按照区间长度进行归纳
基础
$$
\begin{aligned}
f[i,i]+f[i+1,i+1]
=&0 \\
\le & f[i,i+1] \\
\le & f[i,i+1]+f[i+1,i]
\end{aligned}
$$
归纳(Formal Verification)
一方面：
$$
\begin{aligned}
&f[i,j]=f[i,x]+f[x+1,j]+w[i,j] \\
&f[i+1,j+1]=f[i+1,y]+f[y+1,j+1]+w[i+1,j+1] \\
&f[i,j]+f[i+1,j+1] \le
f[i,x]+f[x+1,j] \\
&\quad +f[i+1,y]+f[y+1,j+1]
+w[i,j+1]+w[i+1,j]
\end{aligned}
$$
另一方面：
$$
\begin{aligned}
&f[i,j+1] \ge f[i,x]+f[x+1,j+1]+w[i,j+1] \\
&f[i+1,j] \ge f[i+1,y]+f[y+1,j]+w[i+1,j] \\
&f[i,j+1]+f[i+1,j] \ge f[i,x]+f[x+1,j+1]+ \\
&\quad w[i,j+1]+f[i+1,y]+f[y+1,j]+w[i+1,j]
\end{aligned}
$$
只需要证明（由归纳证明得证）：
$$
f[x+1,j+1]+f[y+1,j] \ge f[x+1,j]+f[y+1,j+1]
$$
Part III
之后证明：$p[i,j-1] \le p[i,j] \le p[i+1,j]$
记 $L=p[i,j-1],M=p[i,j],R=p[i+1,j]$
考虑反证法，只需要分别证明 $p[i,j] < p[i,j-1],p[i+1,j] < p[i,j]$ 都不成立即可
左侧
假设 $p[i,j] < p[i,j-1]$，即 $M < L$
$$
\begin{aligned}
&\begin{cases}
f[M+1,j-1]+f[L+1,j] \le f[M+1,j]+f[L+1,j-1] \\
f[i,M]+f[M+1,j] \le f[i,L]+f[L+1,j]
\end{cases} \\
&\Rightarrow f[i,M]+f[M+1,j-1] \le f[i,L]+f[L+1,j-1]
\end{aligned}
$$
这与 $L=p[i,j-1]$ 矛盾（即 $f[i,L]+f[L+1,j-1] \le f[i,M]+f[M+1,j-1]$）
右侧
假设 $p[i,j]>p[i+1,j]$，即 $M>R$
$$
\begin{aligned}
&\begin{cases}
f[i,R]+f[i+1,M] \le f[i,M]+f[M+1,j] \\
f[i,M]+f[M+1,j] \le f[i,R]+f[R+1,j]
\end{cases} \\
& \Rightarrow f[i+1,M]+f[M+1,j] \le f[i+1,R]+f[M+1,j]
\end{aligned}
$$
这与 $R=p[i+1,j]$ 矛盾（即 $f[i+1,R]+f[R+1,j] \le f[i+1,M]+f[M+1,j]$）
Part IV
前面已经证完了可行决策区间，下面证明总枚举次数是 $O(n^2)$ 的
首先 $p[i,i]=i$，于是有（每行每列单调增）：
$$
\sum_{i < j} p[i+1,j]-p[i,j-1] \le \sum_{i=1}^{n} n=n^2
$$
于是枚举次数是 $O(n^2)$ 的
Part V
若 $w$ 满足四边形不等式，那么哪些 $f$ 也会满足四边形不等式呐？
- $f[i,j]=\min_{i \le k < j} { f[i,k]+f[k+1,j]+w[i,j] }$
- $f[i,j]=\min_{k < j}{ f[i-1,k]+w[k+1,j] }$
- 实际上此时dp是凸的，可以wqs二分
- $f[i]=\min_{j < i}{ f[j]+w[j+1,i] }$
当你发现区间dp的时间复杂度跑不过去但是打表后发现转移位置单调时
石子合并
有 $n(\le 300)$ 堆石子排成一排，现在要求把它们合并成一堆石子，但每次只能合并相邻两堆石子
合并一次的代价是相邻两堆石子的个数之和，现在需要求出把 $n$ 堆石子合并到一起的最小代价
如果 $n \le 5000$ 呐？
$$
\begin{cases}
f[i,j]=\min _ {i \le k < j} { f[i,k]+f[k+1,j]+w[i,j] } \\
w[i,j]=s[i]-s[j-1]
\end{cases}
$$
只需要证 $(w_i-w_{i+1})(j) \le (w_i-w_{i+1})(j+1)$
$$
\begin{aligned}
&LHS=(s[j]-s[i-1])-(s[j]-s[i])=s[i]-s[i-1] \\
&RHS=(s[j+1]-s[i-1])-(s[j+1]-s[i])=s[i]-s[i-1] \\
& \Rightarrow LHS \le RHS
\end{aligned}
$$
可以四边形不等式优化！
[IOI2000]邮局
高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。
邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。
你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。
- 村庄数量为 $V(V \le 3000)$
- 邮局数量为 $P(1 \le P \le 300,P \le V)$
- 村庄位置为 $x_i(1 \le x_i \le 10000)$
设 $f[i,j]$ 表示前 $i$ 个城市里放了 $j$ 个邮局的最小代价
$$
\begin{cases}
f[i,j]=\min_{k < i}{ f[k,j-1]+w[k+1,i] } \\
w[i,j] = w [i,j-1]+x[j]-x\left[\lfloor \frac{i+j}{2} \rfloor\right]
\end{cases}
$$
四边形不等式：$w[i,j]+w[i+1,j+1] \le w[i+1,j]+w[i,j+1]$
$$
\begin{aligned}
&\begin{cases}
w[i,j+1]=w[i,j]+x[j+1]-x[(i+j)/2] \\
w[i+1,j+1]=w[i+1,j]+x[j+1]-x[(i+j+2)/2]
\end{cases} \\
\Rightarrow
&w[i+1,j]+w[i,j+1]-w[i,j]-w[i+1,j+1] \\
=&x[j+1]-x[(i+j)/2]-x[j+1]+x[(i+j+2)/2] \\
=&x[(i+j+2)/2]-x[(i+j)/2] \ge 0
\end{aligned}
$$
E. Ciel and Gondolas
- 给定一个长度为 $n$ 的序列，现在你需要将这个序列划分成连续的 $k$ 段
- 被划分到同一段的两个位置 $i,j$，会产生代价 $a_{ij}$，不同段不会产生代价
- 现在请求出最小的贡献
- $1 \le n \le 4000, 1 \le k \le \min(n, 800), 0 \le u_{ij} \le 9$
$f [ i , j ]$ 前 $i$ 个人用了 $j$ 艘船
$$
\begin{cases}
f [ i , j ] = \min _ {k < i} { f[ k,j - 1 ] + w[k + 1, i] } \\
w[i,j]=(\sum _ {x=i}^{j}\sum _ {y = i}^{j} u[x,y]) \cdot \frac{1}{2}
\end{cases}
$$
四边形不等式：$w[i,j]+w[i+1,j+1] \le w[i+1,j]+w[i,j+1]$
$$
\begin{aligned}
&w[i+1,j]+w[i,j+1]-w[i,j]-w[i+1,j+1] \\
=&\frac{1}{2} (
-\sum_{x=i}^{j}u[x,i]-\sum _ {y=i}^{j}u[i,y]+u[i,i] \\
& + \sum_{x=i}^{j+1}u[x,i]+\sum _ {y=i}^{j+1}u[i,y]-u[i,i]
) \\
=&\frac{1}{2} \left( u[j+1,i]+u[i,j+1] \right) \ge 0
\end{aligned}
$$
Division
- 给定 $n$ 个数字，将它们划分成 $k$ 个集合，每个集合 $S$ 的代价是 $(\max S-\min S)^2$
- 求最小的总代价和
- $n \le 10000, k \le 5000$
先升序排序，然后有：
$$
\begin{cases}
f[i,j]=\min_{k < i} { f[k, j - 1] + w[k+1,i] } \\
w[i,j]=(a[j]-a[i])^2
\end{cases}
$$
四边形不等式：$w[i,j]+w[i+1,j+1] \le w[i+1,j]+w[i,j+1]$
$$
\begin{aligned}
&w[i+1,j]+w[i,j+1]-w[i,j]-w[i+1,j+1] \\
=&(a[j]-a[i+1])^2+(a[j+1]-a[i])^2 \\
&-(a[j]-a[i])^2-(a[j+1]-a[i+1])^2 \\
=&(2a[j]-a[i+1]-a[i])(a[i]-a[i+1]) \\
&+(2a[j+1]-a[i]-a[i+1])(a[i+1]-a[i]) \\
=&(a[i+1]-a[i])(2a[j+1]-2a[j]) \ge 0
\end{aligned}
$$
另一个角度：
$$
\begin{aligned}
f[i,j]
=&\min_{k < i} { f[k, j - 1] + (a[i]-a[k+1])^2 } \\
=&\min_{k < i} { (f[k,j-1]+a[k+1]^2)-2a[i]a[k+1] } + a[i]^2
\end{aligned}
$$
也可以斜率优化
Chef and Bitwise OR Operation
- 给定一个长度为 $n$ 的序列，现在你需要将这个序列划分成连续的 $k$ 段
- 每一段的贡献是这一段所有数的按位或
- 现在请求出最大的贡献
- $1 \le n \le 5000, 1 \le k \le n, 0 \le a_i \le 2^{30}$
$$
\begin{cases}
f[i,j]=\max _ {k < i} { f[k,j-1]+w[k+1,i] } \\
w[i,j]=\mathrm{BITOR}_{k=i}^{j}a[k]
\end{cases}
$$
四边形不等式：$w[i,j]+w[i+1,j+1] \le w[i+1,j]+w[i,j+1]$
$$
\begin{aligned}
&w[i+1,j]+w[i,j+1]-w[i,j]-w[i+1,j+1] \\
=&w[i+1,j]+a[i] \oplus w[i+1,j]\oplus a[j+1]-a[i] \\
& \oplus w[i+1,j]-w[i+1,j]\oplus a[j+1] \\
=&M+L\oplus M \oplus R-L \oplus M -M \oplus R \\
=&M+L\oplus R \oplus M-L\oplus M-R\oplus M
\end{aligned}
$$
只需要考虑每一位
- 若 $L=R=0$，则 $M+M-M-M=0$
- 若 $L=R=1$，则 $M+1-1-1=M-1$
- 寄！！！
- 若 $L=1,R=0$，则 $M+1-1-M=0$
换而言之，看这组数据：
1 | 1 0 0 1 |
$w[1,3]+w[2,4]=2 > 1=w[2,3]+w[1,4]$
很遗憾，$w$ 不满足四边形不等式，那怎么做？
但，真的不满足吗？
另一个角度：
$$
\begin{cases}
f[i,j]=\min _ {k < i} { f[k,j-1]+w[k+1,i] } \\
w[i,j]=-\mathrm{BITOR} _ {k=i}^{j}a[k]
\end{cases}
$$
$$
\begin{aligned}
&w[i+1,j]+w[i,j+1]-w[i,j]-w[i+1,j+1] \\
=&-M-L\oplus R \oplus M+L\oplus M+R\oplus M
\end{aligned}
$$
考虑每一位
- 若 $L=R=0$，则 $-M-M+M+M=0$
- 若 $L=R=1$，则 $-M-1+1+1=1-M \ge 0$
- 这回没问题了
- 若 $L=1,R=0$，则 $-M-1+1+M=0$
哪里出了问题？
- $f=\max \cdots$
- $f=\min \cdots$
之前用了两个式子：
$$
\begin{aligned}
&f[i,M]+f[M+1,j] \le f[i,L]+f[L+1,j] \\
&f[i,M]+f[M+1,j] \le f[i,R]+f[R+1,j]
\end{aligned}
$$
这里默认了 $f=\min \cdots$，于是引发了上面的问题
解决方案：让 $w$ 变成 $-w$，这样就可以把 $\max$ 翻转成 $\min$
上面的算法是 $O(n^2+nk)$ 的，如果 $k$ 比较小呢？
