基础 dp。

四边形不等式优化 dp

参考文章。

在成本函数 w(j,i)w(j, i) 中，若对于任意 a≤b≤c≤da \le b \le c \le d 均有

w(a,d)+w(b,c)≥w(a,c)+w(b,d)w(a, d) + w(b, c) \ge w(a, c) + w(b, d)

则称函数 ww 四边形不等式。

简单描述为：交叉小于包含。

等价形式

在满足四边形不等式的函数 ww 中，对于任意 j<ij < i 均有

w(j,i+1)+w(j+1,i)≥w(j,i)+w(j+1,i+1)w(j, i+1) + w(j+1, i) \ge w(j, i) + w(j+1, i+1) w(j,i)−w(j,i−1)≥w(j−1,i)+w(j−1,i−1)w(j, i) - w(j, i-1) \ge w(j-1, i) + w(j-1, i-1)

对于转移方程：

fi=max⁡fj+w(j,i)f_i=\max f_j + w(j,i)

如果满足：

w(j,i)−w(j,i−1)≥w(j−1,i)+w(j−1,i−1)w(j, i) - w(j, i-1) \ge w(j-1, i) + w(j-1, i-1)

那么：

w(j−1,i−1)−w(j,i−1)≥w(j−1,i)−w(j−1,i−1)w(j-1,i-1)-w(j,i-1)\ge w(j-1,i)-w(j-1,i-1)

如果在 i−1i-1 处 jj 比 j−1j-1 优，那么在 ii 处 jj 仍然比 j−1j-1 优。

因为：

fj−1+w(j−1,i−1)≤fj+w(j,i−1)f_{j-1}+w(j-1,i-1)\le f_j+w(j,i-1)

所以减去上式仍然成立：

fj−1+w(j−1,i)≤fj+w(j,i)f_{j-1}+w(j-1,i)\le f_j+w(j,i)
w(a,d)+w(b,c)≥w(a,c)+w(b,d)w(a, d) + w(b, c) \ge w(a, c) + w(b, d) 证明

四边形不等式与决策单调性

若函数 ww 满足四边形不等式，则最优化问题

dp[i]=min⁡0≤j<i{dp[j]+w(j,i)}dp[i] = \min_{0 \le j < i} \{ dp[j] + w(j, i) \}

满足决策单调性，即最优决策点 p[i]p[i] 满足 p[i]≤p[i+1]p[i] \le p[i+1]。

证明： 对于任意 j2<opti1j_2 < opt_{i_1} 且 opti1,j2opt_{i_1}, j_2 为候选决策点，由最优性均有

dp[opti1]+w(opti1,i)≤dp[j2]+w(j2,i)（若 opti1 优于 j2 时成立）dp[opt_{i_1}] + w(opt_{i_1}, i) \le dp[j_2] + w(j_2, i) \quad \text{（若 $ opt_{i_1} $ 优于 $ j_2 $ 时成立）}

同时，对于任意 i1<i2i_1 < i_2，由四边形不等式可得

w(opti1,i2)+w(j2,i1)≥w(opti1,i1)+w(j2,i2)w(opt_{i_1}, i_2) + w(j_2, i_1) \ge w(opt_{i_1}, i_1) + w(j_2, i_2)

移项得

w(j2,i1)−w(j2,i2)≥w(opti1,i1)−w(opti1,i2)w(j_2, i_1) - w(j_2, i_2) \ge w(opt_{i_1}, i_1) - w(opt_{i_1}, i_2)

将上述两个不等式（最优性条件与四边形不等式导出式）相加，经过整理可推出

dp[opti1]+w(opti1,i2)≤dp[j2]+w(j2,i2)dp[opt_{i_1}] + w(opt_{i_1}, i_2) \le dp[j_2] + w(j_2, i_2)

即 opti1opt_{i_1} 对 i2i_2 依然不劣于 j2j_2，从而决策点随 ii 增大单调不减，得证。

P4767 [IOI 2000] 邮局 加强版

P4767 [IOI 2000] 邮局 加强版。

wqs 二分

主要的思想就是 f(x)f(x) 关于 xx 的图像的斜率单调。

P5633 最小度限制生成树

P5633 最小度限制生成树。

通过这道题来讲一下。

f(x)f(x) 表示 ss 连接了 xx 条边的答案。然后我们发现 ff 斜率单调。

我们先求出 MST 时候的 ff，是最小值，然后向 xx 方向一步一步移动。我们用带权二分，二分一个偏移量，就是连接 ss 边的权值全部加上一个值（可以为负）以控制连接 ss 边的数量。

这也就相当于二分切线的斜率，截距 b=f(x)−cxb=f(x)−cx，cc 表示偏移量。

因为 −cx-cx，所以我们可以画一条线，斜率为 cc，在原图上放着就行了。我们需要使得当前的 xx 为凸包上的顶点，也就是最优的。

看上去这就是两种理解方法。

练习题

P5574 [CmdOI2019] 任务分配问题

P5574 [CmdOI2019] 任务分配问题。

决策单调性。

思路

fi,jf_{i,j} 表示把前 ii 个数分成 jj 段的最小代价。

fi,j=min⁡k=1i−1fj−1,k+cost(k,i)f_{i,j}=\min_{k=1}^{i-1}f_{j-1,k}+cost(k,i)

我们发现这个过不了，需要优化。

然后可以发现，这有决策单调性，于是就解决了。

这个决策单调性的写法不错，直接分治递归下去。