Dyd's Blog

He who has a strong enough why can bear almost any how.

优化dp3

Posted on Edited on In
Symbols count in article: 13k Reading time ≈ 12 mins.

然而我 dp 废的一比（四大皆空）

优化dp3

书接上回：优化dp2

四边形不等式优化

以下未特殊说明，就认为 $w(x, y)$ 是定义在整数集合上的二元函数，下面的 $\ge, >$ 是对于 $\min$ 形转移来说的，如果 dp 方程要求的是 $\max$ ，则应该反过来（但其实你定义函数时取个负也行）

定义

对于任意的 $a \le b \le c \le d$ ，若有 $w(a, d) + w(b, c) \ge w(a, c) + w(b, d)$ ，则称 $w(x, y)$ 满足四边形不等式（蒟蒻个人的记忆方法为“两边加中间大于错位相加”）

对于任意的 $l \le l’ \le r’ \le r$ ，若有 $w(l, r) \ge w(l’, r’)$ ，就称 $w(x, y)$ 满足区间包含单调性（蒟蒻个人的记忆方法为“大区间大于小区间”）

判定定理

这里有一个定理（或者说是四边形不等式的另外一个形式）：

$w(x, y)$ 满足四边形不等式的充要条件是：对于任意的 $a < b$ （注意这里不取等），有 $w(a, b + 1) + w(a + 1, b) \ge w(a, b) + w(a + 1, b + 1)$ （蒟蒻个人的记忆方法为“分开加大于同进退”）

必要性显然，下面证明充分性：

对于 $a < c$ 有 $w(a, c + 1) + w(a + 1, c) \ge w(a, c) + w(a + 1, c + 1)$

对于 $a + 1 < c$ 有 $w(a + 1, c + 1) + w(a + 2, c) \ge w(a + 1, c) + w(a + 2, c + 1)$

两式相加，得 $w(a, c + 1) + w(a + 2, c) \ge w(a, c) + w(a + 2, c + 1)$

以此类推，对于任意的 $a \le b \le c$ 有 $w(a, c + 1) + w(b, c) \ge w(a, c) + w(b , c + 1)$

同理，对于任意的 $a \le b \le c \le d$ 有 $w(a, d) + w(b, c) \ge w(a, c) + w(b, d)$

QED

1D/1D 的四边形不等式优化

还是来看 1D/1D 型 dp 方程：
$$
d[i] = \min_{l(i) \le j \le r(i)} (d[j] + val(i, j))
$$
我们记 $bp[i]$ （ best pos ）表示 $d[i]$ 的最优决策点，即使 $d[i]$ 取得最小的 $j$ 的值，若 $bp$ 单调（不要求严格）且 $l(i), r(i)$ 也单调，则称 $d$ 具有决策单调性

1D 决策单调性定理

对于 1D/1D 型 dp 方程： $d[i] = \min_{l(i) \le j \le r(i)} (d[j] + val(i, j))$ ，若 $val(i, j)$ 满足四边形不等式，且 $r(i) \le i$ ，则 $d$ 具有决策单调性

证明：
$$
\begin{aligned}
& \forall i \in [1, n], \forall j \in [l(i), bp[i] - 1]由 bp[i] 的最优性可得: \\
& d[bp[i]] + val(i, bp[i]) \le d[j] + val(i, j) & (1) \\
& \forall k \in [i + 1, n], 由四边形不等式得: \\
& val(k, j) + val(i, bp[i]) \ge val(i, j) + val(k, bp[i]) \\
& val(k, bp[i]) - val(i, bp[i]) \le val(k, j) - val(i, j) & (2) \\
(1) + (2) 得: \\
& d[bp[i]] + val(k, bp[i]) \le d[j] + val(k, j)
\end{aligned}
$$
也就是说， $\forall k > i$ ，以 $bp[i]$ 做为决策一定比以 $j < bp[i]$ 作为决策优（或者相等），所以 $k$ 的最优决策不可能小于 $bp[i]$ ，即 $bp[k] \ge bp[i]$ ，则 $bp$ 单调递增，故 $d$ 具有决策单调性（但这里一定要有 $l(i), r(i)$ 也单调，否则可能出现 $bp[i]$ 不能做 $k$ 的决策，但 $j$ 可以的情况）

QED

所以，四边形不等式优化 1D/1D dp 的方法其实就是推出决策单调性，然后用单调性维护（这里有一个蒟蒻专用技巧，那就是直接猜它有单调性，这样就可以直接做了 蒟蒻的挣扎 ，不行还可以先打个暴力 dp 然后把最优决策输出来看看有没有单调性）当 $d$ 具有决策单调性时，我们可以把 $O(n^2)$ 的 1D/1D dp 优化到 $O(n \log n)$ （这里未考虑计算 $val$ 的时间）

队列 + 二分

一般可以用队列 + 二分：

考虑对于 $bp$ 进行维护，我们每次直接修改 $bp$ 数组是很低效的，我们维护若干个三元组 $(j, l, r)$ ，表示“在 $i \in [l, r]$ 时， $j$ 是最优决策，即 $bp[l \sim r] = j$ ”然后用队列维护，对于每个 $i$ ，进行如下操作：

  • 检查队头三元组 $(j _0, l _0, r _0)$ ，若 $r _0 < i$ 删除队头，否则令 $l_0 = i$
  • 取队头的 $j$ 为最优决策进行转移
  • 尝试插入决策 $i$ ，初始化 $pos = r_t + 1$ ，其中 $r_t$ 为队尾三元组执行如下步骤：
    1. 取出队尾，记为 $(j _t, l _t, r _t)$
    2. 若对于 $d[l _t]$ 决策 $i$ 优于 $j$ ，删除队尾，记 $pos = l _t$ ，回到第 $1$ 步
    3. 否则，若对于 $d[r _t]$ ， $j$ 优于 $i$ ，去向第 $5$ 步
    4. 否则，在 $[l _t, r _t]$ 上二分一个位置 $pos$ ，把 $r _t$ 赋为 $pos - 1$ ，去第 $5$ 步
    5. 把三元组 $(i, pos, n)$ 插入队尾

不难发现每个 $i$ 最多出/如队一次， $\log n$ 消耗在二分上

分治

有一种特殊情况，如果 dp 方程是与 $d[j]$ 无关的，即：
$$
d[i] = \min_{l(i) \le j \le r(i)} (val(i, j))
$$
其中 $val(i, j)$ 不含有关 $d[j]$ 的项，那么我们可以用分治

要注意，这里的“无关于 $d[j]$ ”指的是“无关于本层的 $d[j]$ ”，如果 dp 状态还有几维，而在把外层变量当常量后，前几层的 $d[j]$ 已经计算完毕，也是常量，就可以用了（关于为什么，可以看下面）

设函数 sol(l, r, L, R) 表示“当然正在处理 $d[l \sim r]$ ，最优决策存在于区间 $[L, R]$ ”，函数伪代码如下：

1
2
3
4
5
6
7
8
9
10
sol(l, r, L, R)
	if (l > r || L > R) return 
	mid <- l + r >> 1
	for i : L -> R
		找到最优决策点 pos 
	end for
	用 pos 跟新 d[mid]
	sol(l, mid - 1, L, pos)
	sol(mid + 1, r, pos, R)
end sol

很明显（分治好打的多）共会递归 $\log n$ 层，每层一共会扫一个 $n$ ，总共是 $O(n \log n)$

现在我们来看为什么要保证方程无关于本层的 $d[j]$ ，其实这很明显，我们是跟新完 $d[mid]$ 再去求 $d[l \sim mid - 1]$ 和 $d[mid + 1 \sim r]$ 的，所以我们跟新 $d[mid]$ 时，本层其它的 $d$ 根本还没算，怎么能用呢？

由此可以看出，队列 + 二分的方法泛用性更广，但考虑到分治的过程中可以同时计算一些信息（如 $val$ 或者题目中的其它问题）有些题用分治会更好

例题九

诗人小G

老经典题了

思路

首先记 $len[i]$ 为第 $i$ 句诗的长度， $sum[i]$ 为 $len[i]$ 的前缀和，设 $d[i]$ 表示“前 $i$ 句诗的最小不协调度”，有：
$$
d[i] = \min _{0 \le j < i} (d[j] + (\mid sum[i] - sum[j] + i - j - 1 - L \mid)^P)
$$
其中 $i - j - 1$ 是空格的个数

典型的 1D/1D ，为简单记 $f(i) = sum[i] + i$ ，有 $val(i, j) = (\mid f(i) - f(j) - (1 + L) \mid)^P$ 很明显由于次数过高，无法斜率优化，考虑四边形不等式

用判定定理， $\forall a < b$ ，我们要证明 $val(a, b + 1) + val(a + 1, b) \ge val(a, b) + val(a + 1, b + 1)$

变形：
$$
\begin{aligned}
val(a, b + 1) + val(a + 1, b) & \ge val(a, b) + val(a + 1, b + 1) \\
(\mid f(a) - f(b + 1) - (1 + L) \mid)^P + (\mid f(a + 1) - f(b) - (1 + L) \mid)^P & \ge (\mid f(a) - f(b) - (1 + L) \mid)^P + (\mid f(a + 1) - f(b + 1) - (1 + L) \mid)^P \\
因为 f(x + 1) & = f(x) + len[x + 1] + 1 \\
故化为: \\
(\mid f(a) - f(b + 1) - (1 + L) \mid)^P + (\mid f(a) - f(b) - (1 + L) + len[a + 1] + 1 \mid)^P & \ge (\mid f(a) - f(b) - (1 + L) \mid)^P + (\mid f(a) - f(b + 1) - (1 + L) + len[a + 1] + 1 \mid)^P \\
记 u = f(a) - f(b) - (1 + L), v = f(a) - f(b + 1) &- (1 + L) , t = len[a + 1] + 1\\
明显有 v = u - len[b + 1] - 1 & < u \\
于是原式化为: \\
(\mid v \mid)^P + (\mid u + t\mid)^P & \ge (\mid u \mid)^P + (\mid v + t \mid)^P \\
(\mid v \mid)^P - (\mid v + t \mid)^P & \ge (\mid u \mid)^P - (\mid u + t\mid)^P \\
\end{aligned}
$$
那么，我们只要证明函数 $g(x) = (\mid x \mid)^P - (\mid x + c \mid)^P$ （其中 $P, c$ 是常数）为减函数，则四边形不等式得证

而证明减函数只要分类讨论去掉绝对值，然后求导就可以了（分类讨论太长，这里就不打了）

无论如何，我们证得原函数满足四边形不等式，可得决策单调性

至于维护，本题方程中用到了本层的其它 $d$ （废话，一共只有一层啊），所以不能分治，我们采用队列 + 二分

代码

细节颇多，输出格式尤其要注意（行末没有空格！）

另外中间转移时会炸 long long 开 __int128 也不行，只能开 long double 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define LD long double
using namespace std;
const int N = 1e5 + 5, S = 35;
const LD INF = 1e18;
int n, L, P, sum[N], h, t, from[N];
char s[N][S];
struct Date{ int bp, l, r; } q[N];
LD d[N];
LD qpow(LD x, int y)
{
    LD res = 1;
    for (; y; x *= x, y >>= 1) if (y & 1) res *= x;
    return res;
}
LD calc(int i, int j){ return d[j] + qpow(abs(sum[i] - sum[j] + i - j - 1 - L), P); } //dp方程
void print(int l, int r)
{
    if (l != 1) print(from[l - 1] + 1, l - 1);
    for (int i = l; i < r; ++i) printf("%s ", s[i] + 1);
    printf("%s\n", s[r] + 1); //行末不空格
}
int main()
{
    int T;
    for (scanf("%d", &T); T--; puts("--------------------"))
    {
        scanf("%d %d %d", &n, &L, &P);
        for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1), sum[i] = strlen(s[i] + 1) + sum[i - 1];
        q[h = t = 1] = {0, 1, n};
        for (int i = 1, pos; i <= n; ++i)
        {
            for (; h <= t && q[h].r < i; ++h);
            d[i] = calc(i, q[h].bp), from[i] = q[h].bp;
            for (pos = n + 1; h <= t && calc(q[t].l, i) <= calc(q[t].l, q[t].bp); pos = q[t--].l);
            if (h <= t && calc(q[t].r, i) <= calc(q[t].r, q[t].bp))
            {
                int l = q[t].l, r = q[t].r, mid;
                while (l <= r)
                {
                    mid = l + r >> 1;
                    calc(mid, i) <= calc(mid, q[t].bp) ? r = (pos = mid) - 1 : l = mid + 1;
                }
                q[t].r = pos - 1;
            }
            if (pos <= n) q[++t] = {i, pos, n};
        }
        if (d[n] > INF) puts("Too hard to arrange");
        else printf("%.0Lf\n", d[n]), print(from[n] + 1, n);
    }
	return 0;
}

例题十

Ciel and Gondolas

题目大意

有 $n \le 10^5$ 个数（记为 $a_i$ ），要将它们划分成连续的 $k \le 20$ 段，每段的代价是该段中相同元素的对数，求所有子段的费用之和的最小值

思路

明显的区间 dp ，先写方程，设 d[i, j] 表示“前 $i$ 个数分成 $j$ 段的最小代价”，明显，设 $val(l, r)$ 表示“ $[l, r]$ 中相同的数的对数”，有：
$$
d[i, j] = \min _{0 \le k < i} (d[k, j - 1] + val(k + 1, i))
$$
如果直接 dp ，时间明显是 $O(n^2 k * O(计算val(k + 1, i)))$

呃呃，先把 $O(计算val(k + 1, i))$ 放一下，因为在如何 dp 不确定的情况下，我们也不太好考虑如何计算 $val$ （当然，暴力计算挂的死死的）

明显 $j$ 做外层循环，这就又是个 1D/1D ，我们连如何算 $val$ 都不知道，当然没法斜率优化，考虑四边形不等式

我们要证明，对于任意的 $i < j$ ，有 $val(i, j + 1) + val(i + 1, j) \ge val(i, j) + val(i + 1, j + 1)$

设区间 $[i + 1, j]$ 中有 $x$ 个数与 $a_i$ 相同，有 $y$ 个数与 $a_{j + 1}$ 相同

我们要证：
$$
(x + y + [a_i == a_{j + 1}] + val(i + 1, j)) + val(i + 1, j) \ge (x + val(i + 1, j)) + (y + val(i + 1, j))
$$
（其中 $[…]$ 表示“当 $…$ 成立时为 $1$ ”）

而上式正确性显然，故 $val$ 满足四边形不等式，决策具有单调性，理论上来讲，我们可以把 dp 的时间从 $O(n^2 k)$ 优化到 $O(n k \log n)$ ，观察数据范围，我们希望 $O(计算val(k + 1, i))$ 要做到 $O(1)$

预处的想法是不行的，因为 $n \le 10^5$ 太大了存不下，所以我们只能每次直接求，但每次扫区间很明显是挂了的，我们考虑用上次的 $val$ 计算这次的 $val$ ，发现“统计区间内”是莫队的经典问题，考虑像莫队一样维护双指针，但莫队的时间复杂度有保证是因为调整了询问的顺序，所以我们也想到调整 dp 顺序

观察方程，不难发现， $d[i, j]$ 与 $d[k, j]$ 无关（只由 $d[k, j - 1]$ 转移），于是可以用分治的方法，而选择分治的好处在于分治的计算顺序恰好可以保证莫队的时间复杂度，简证如下：

首先，对于分治的每一层单独来看（就不考虑进入下一层的情况，直接把本层的连起来，类似 sort 的分析方法），会发现两个指针在每一层一定最多扫过每个元素各一遍（因为在每一层，两个指针都是单调的），有 $\log n$ 层，故层内指针总共移动 $O(n \log n)$ 次

再考虑进入下一层/从下一层返回的额外移动，设 $(l, r, L, R)$ 表示当前计算区间为 $d[l \sim r]$ ，最优决策存在于区间 $[L, R]$ ，设最优决策为 $pos$ ，设 $mid = l + r >> 1$ ，设双指针为 $il, ir$ 在这个区间计算完成后，一定有 $il = pos + 1, ir = mid$ （ $il$ 要加一，原因自己去看方程），而下一层 $(l, mid - 1, L, pos)$ 开始时会把指针移动到 $il = L + 1, ir = (l + mid - 1) >> 1$ ，两个指针移动的距离都小于等于当前区间长度 $r - l + 1$ ，从左区间回来时先把两个指针移回（显然耗时与移去相同），再进入右区间 $(mid + 1, r, pos, R)$ ，开始时会把指针移动到 $il = pos, ir = (mid + 1 + r) >> 1$ 两个指针移动的距离也都小于等于当前区间长度 $r - l + 1$ ，故对于当前区间，进入下一层/从下一层返回的额外移动是 $O(r - l + 1)$ 级的；每层区间的长度加起来等于 $n$ ，故每层进入下一层/从下一层返回的额外移动是 $O(n)$ 级的，而一共有 $\log n$ 层，故额外的移动总时间也是 $O(n \log n)$ 的

本题就体现了分治的优势，在题目转移顺序允许分治的情况下，分治的计算顺序为我们计算额外信息提供便利，且代码也好打

代码

明显 $j$ 可以滚动压掉

注意转移时用的是 $val(k + 1, i)$ ，而决策点是 $k$ ，所以注意 $0 \le k < i$

关于 $0$ ，要注意 d[0][0] = 0 ，而其它 d[i][0] = INF （明显把 $i$ 个人分成 $0$ 段方案不存在）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 5;
const LL INF = 1e18;
int a[N], n, k, o;
LL d[N][2];
namespace MD //莫队
{
    int cnt[N], il = 1, ir = 0;
    LL val;
    LL calc(int l, int r) //把指针移动到[l, r]
    {
        for (; il < l; val -= --cnt[a[il++]]);
        for (; il > l; val += cnt[a[--il]]++);
        for (; ir < r; val += cnt[a[++ir]]++);
        for (; ir > r; val -= --cnt[a[ir--]]);
        return val;
    }
}
void sol(int l, int r, int L, int R)
{
    if (l > r || L > R) return ;
    int mid = l + r >> 1, pos = L;
    LL t;
    d[mid][o ^ 1] = INF;
    for (int i = L, Rr = min(R, mid - 1); i <= Rr; ++i)
        if ((t = d[i][o] + MD::calc(i + 1, mid)) < d[mid][o ^ 1]) d[mid][o ^ 1] = t, pos = i;
    sol(l, mid - 1, L, pos), sol(mid + 1, r, pos, R);
}
int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), d[i][0] = d[i][1] = INF;
    d[0][o] = 0;
    for (int i = 1; i <= k; ++i, o ^= 1) sol(1, n, 0, n - 1); //这里减1
    printf("%lld\n", d[n][o]);
    return 0;
}

2D/1D 的四边形不等式优化

如果只是优化 1D/1D dp，四边形不等式显然不是很强，所以我们来看看更高维的 dp

2D/1D dp 的方程模型如下：
$$
d[i, j] = \min_{l(i, j) \le k \le r(k, j)} (d[i, k] + d[k + 1, j] + val(i, j))
$$
其中 2D 指枚举的状态数， 1D 指枚举的决策数，最典型的是区间 dp ，明显，直接 dp 时间为 $O(n^3)$ （一定要注意 $val(i, j)$ 与 $k$ 无关）

警告！下面的证明都很繁琐且没啥用（完全不影响做题），可以只记结论

2D 状态四边形不等式判定

对于 2D/1D dp 的方程：
$$
d[i, j] = \min_{l(i, j) \le k \le r(k, j)} (d[i, k] + d[k + 1, j] + val(i, j))
$$
若 $val$ 满足四边形不等式和区间包含单调性（忘了的回去翻定义）， $d$ 满足 $d[i, i] = val(i, i) = 0$ ，且 $i \le l(i, j) \le r(i, j) < j$ 则 $d[i, j]$ 满足四边形不等式

证明（又臭又长）：

当 $j = i + 1$ 时， $d[i, j + 1] + d[i + 1, j] = d[i, i + 2] + d[i + 1, i + 1]$ ，又因为 $d[i + 1, i + 1] = 0$ ，故 $d[i, j + 1] + d[i + 1, j] = d[i, i + 2]$

由于 $i \le l(i, j) \le r(i, j) < j$ ， $d[i, i + 2]$ 的决策最多只有 $i$ 和 $i + 1$

  1. 若 $d[i, i + 2]$ 的最优决策为 $i + 1$ ，则
    $$
    d[i, i + 2] = d[i, i + 1] + d[i + 2, i + 2] + val(i, i + 2) = d[i, i + 1] + val(i, i + 2)
    $$
    ，发现 $d[i, i + 1]$ 的决策只有 $i$ ，故 $d[i, i + 1] = d[i, i] + d[i + 1, i + 1] + val(i, i + 1) = val(i, i + 1)$ ，综合两式，有 $d[i, i + 2] = val(i, i + 1) + val(i, i + 2) = d[i, j + 1] + d[i + 1, j]$

    同样因为 $d[i, i] = 0$ ，有 $d[i, i + 1] + d[i + 1, i + 2] = val(i, i + 2) + val(i + 1, i + 2) = d[i, j] + d[i + 1, j + 1]$

    由于 $val$ 满足四边形不等式，有 $val(i, i + 1) + val(i, i + 2) \ge val(i, i + 1) + val(i + 1, i + 2)$

    故 $d[i, j + 1] + d[i + 1, j] \ge d[i, j] + d[i + 1, j + 1]$ ，即 $d$ 满足四边形不等式

  2. 若 $d[i, i + 2]$ 的最优决策为 $i$ ，同理有
    $$
    d[i, i + 2] = d[i, i] + d[i + 1, i + 2] + val(i, i + 2) = d[i + 1, i + 2] + val(i, i + 2) = val(i + 1, i + 2) + val(i, i + 2)
    $$
    $d[i + 1, i + 2] + d[i, i + 1] = val(i + 1, i + 2) + val(i, i + 1) = d[i + 1, j + 1] + d[i, j]$

    同样由 $val$ 满足四边形不等式，得 $d[i, j + 1] + d[i + 1, j] \ge d[i, j] + d[i + 1, j + 1]$

综上，当 $j = i + 1$ ，即 $j - i = 1$ 时， $d$ 满足四边形不等式

假设当 $j - i < k$ 时四边形不等式成立，下面证明 $j - i = k$ 时成立

设 $d[i, j + 1]$ 最优决策为 $x$ ， $d[i + 1, j]$ 最优决策为 $y$

有等式 $(1)$ ：
$$
d[i, j + 1] + d[i + 1, j] = d[i, x] + d[x + 1, j + 1] + val(i, j + 1) + d[i + 1, y] + d[y + 1, j] + val(i + 1, j)
$$
而对于 $d[i, j]$ 和 $d[i + 1, j + 1]$ ， $x, y$ 就不一定是最优决策了

当 $x \le y$ 时，取 $x$ 为 $d[i, j]$ 的决策， $y$ 为 $d[i + 1, j + 1]$ 的决策，由不优得不等式 $(2)$ ：
$$
d[i, x] + d[x + 1, j] + val(i, j) + d[i + 1, y] + d[y + 1, j + 1] + val(i + 1, j + 1) \ge d[i, j] + d[i + 1, j + 1]
$$
$(1) + (2)$ 得 $(3)$ ：
$$
\begin{aligned}
d[i, x] + d[x + 1, j] + val(i, j) + d[i + 1, y] + d[y + 1, j + 1] + val(i + 1, j + 1) + d[i, j + 1] + d[i + 1, j] & \ge d[i, j] + d[i + 1, j + 1] + d[i, x] + d[x + 1, j + 1] + val(i, j + 1) + d[i + 1, y] + d[y + 1, j] + val(i + 1, j) \\
d[x + 1, j] + d[i + 1, y] + d[y + 1, j + 1] + d[i, j + 1] + d[i + 1, j] + val(i, j) + val(i + 1, j + 1) & \ge d[i, j] + d[i + 1, j + 1] + d[x + 1, j + 1] + d[y + 1, j] + val(i, j + 1) + val(i + 1, j) \\
\end{aligned}
$$
有 $x + 1 \le y + 1 \le j < j + 1$ ，由归纳假设，有 $d[x + 1, j + 1] + d[y + 1, j] \ge d[x + 1, j] + d[y + 1, j + 1]$ ，结合 $val$ 满足四边形不等式，与 $(3)$ 比较得：
$$
d[i, j + 1] + d[i + 1, j] \ge d[i, j] + d[i + 1, j + 1]
$$
则 $j - i = k$ 时满足四边形不等式；

当 $x \ge y$ 时，取 $y$ 为 $d[i, j]$ 的决策， $x$ 为 $d[i + 1, j + 1]$ 的决策，同理可证得 $j - i = k$ 时满足四边形不等式

由数学归纳法原理，原命题得证

QED

2D 决策单调性定理

对于 2D/1D dp 的方程：
$$
d[i, j] = \min_{l(i, j) \le k \le r(k, j)} (d[i, k] + d[k + 1, j] + val(i, j))
$$
记 $d[i, j]$ 的最优决策点为 $bp[i, j]$ ，若 $\forall i < j$ 有 $bp[i, j - 1] \le bp[i, j] \le bp[i + 1, j]$ ，则称 $d$ 具有决策单调性

若 $d$ 满足 $d[i, i] = val(i, i) = 0$ ， $i \le l(i, j) \le r(i, j) < j$ ，且 $d$ 满足四边形不等式，则 $d$ 具有决策单调性

证明：

记 $p = bp[i, j]$ ，则 $\forall i < k \le p$ ，因为 $d$ 满足四边形不等式，有：
$$
\begin{aligned}
d[i, p] + d[i + 1, k] & \ge d[i, k] + d[i + 1, p] \\
d[i + 1, k] - d[i + 1, p] & \ge d[i, k] - d[i, p] \\
\end{aligned}
$$
又由 $p$ 的最优性（带 dp 方程消去 $val$ 可得）：
$$
\begin{aligned}
d[i, k] + d[k + 1, j] & \ge d[i, p] + d[p + 1, j] \\
d[i, k] - d[i, p] + d[k + 1, j] - d[p + 1, j] & \ge 0 \\
\end{aligned}
$$
考虑对于 $d[i + 1, j]$ 用 $k$ 为决策减用 $p$ 为决策：
$$
\begin{aligned}
& (d[i + 1, k] + d[k + 1, j] + val(i + 1, j)) - (d[i + 1, p] + d[p + 1, j] + val(i + 1, j)) \\
= & (d[i + 1, k] - d[i + 1, p]) + (d[k + 1, j] - d[p + 1, j]) \\
\ge & (d[i, k] - d[i, p]) + (d[k + 1, j] - d[p + 1, j]) \\
\ge & 0
\end{aligned}
$$
也就是说，对于 $d[i + 1, j]$ ， $p$ 比任意 $k \le p$ 更优，故 $bp[i + 1, j] \ge bp[i, j]$ ，同理可证明 $bp[i, j - 1] \le bp[i, j]$

QED

实现

2D/1D 的实现没有 1D/1D 那么花里胡哨，就是直接记录 $bp$ ，对于 $d[i, j]$ ，只在 $bp[i, j - 1] \le k \le bp[i + 1, j]$ 的范围枚举 $k$ 维护 $d, bp$

时间也很好分析：
$$
\begin{aligned}
& \sum _{i = 1}^{n - 1} \sum _{j = i + 1}^{n} (bp[i + 1, j] - bp[i, j - 1] + 1) \\
= & \sum _{i = 1} ^ {n - 1} (bp[i + 1, n] - bp[1, n - i] + n - i) \\
\le & n^2
\end{aligned}
$$
故时间复杂度优化到了 $O(n^2)$

你可能觉得似乎没有 1D/1D 优化的厉害，但其实， 1D/1D 状态数是 $O(n)$ 的，四边形不等式把转移从 $O(n)$ 优化到了 $O(\log n)$ （斜率优化在最简单的情况下可以优化到 $O(1)$ ，最麻烦情况下只有 $O(\log^2 n)$ ）；而 2D/1D 状态数是 $O(n^2)$ 的，四边形不等式把转移从 $O(n)$ 直接优化到 $O(1)$ ，作为对转移的优化，已经非常优秀了（事实上，如果你不考虑重新设计状态/排除无用状态， $O(n^2)$ 已经是最好复杂度了）

最后提醒一点：以上的复杂度分析都没有考虑计算 $val$ 的复杂度！（这一点从例题十中也能看出）

例题十一

一个古老的石头游戏

题意同“石子合并”，但要求 $O(n^2)$ ，太经典了，就是板子

话说好像有 $O(n \log n)$ 做法，但那和我们要讲的没关系了……

艹，好像数据加强了， $O(n^2)$ 过不了了！ shit ！

思路

呃呃，还要思路吗？

写个方程吧：设 $d[i, j]$ 表示“合并区间 $[i, j]$ 的最小代价”，转移有：
$$
d[i, j] = \min _{i \le k < j} (d[i, k] + d[k + 1, j]) + \sum _{t = i}^j a _t
$$
$val(i, j)$ 显然可以前缀和做到 $O(1)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using LL = long long;
const int N = 5000 + 5, INF = 1e9 + 5;
int n, a[N], d[N][N], bp[N][N];
LL sum[N];
int main()
{
    for (; scanf("%d", &n), n; sum[0] = 0, printf("%d\n", d[1][n]))
    {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i], d[i][i] = 0, bp[i][i] = i;
        for (int len = 2; len <= n; ++len)
            for (int i = 1, j, k; i <= n; ++i)
                for (d[i][j = i + len - 1] = INF, k = bp[i][j - 1]; k <= bp[i + 1][j] && k < j; ++k)
                    if (d[i][k] + d[k + 1][j] + sum[j] - sum[i - 1] < d[i][j]) d[i][j] = d[i][bp[i][j] = k] + d[k + 1][j] + sum[j] - sum[i - 1];
    } 
    return 0;
}

2D/1D 的另一种形式?

如下
$$
d[i, j] = \min (d[k, j - 1] + val(k + 1, i))
$$
你会发现其实就是例题十，优化方式也一样，但有些地方把它归类为 2D/1D 优化，可能是因为状态是 $O(n^2)$ 的，但这里还是决定把它归为 1D/1D ，因为外层的 $j$ 我们是当常量的，优化方式也更像（或者说就是） 1D/1D 型

废话 + 待续

解决完四边形不等式，就还剩凸优化一个大点和其它一些小点了，慢慢搞吧

优化dp4