Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

区间dp

Posted on

讲课，ps

什么是区间dp

区间 $dp$ 就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的 $dp$ 算法（实际上不需要是最优解）。

石子合并问题

有若干个石子排成一行，每个石子有一定的质量，现在要将它们合并成一堆，每一次合并产生的价值是两堆石子的质量和（只能合并相邻的石子），求最大/最小价值。

以最小值为例，对于这个问题，如果我们用$f_{i, j}$表示从$i$到$j$的代价最小值，那么这一块区域可以被分割成两个小的区域，通过不断调整分割点，我们就可以找到$f_{i, j}$，转移方程如下：
$$
f_{i, j} = \min(f_{i, j}, f_{i, k} + f_{k + 1, j} + s[j] - s[i - 1]) (i \le k < j)
$$
初始值：
$$
f_{i, i} = 0
$$
时间复杂度$O(n ^ 3)$。

如果石子排成了一个环呢？

环形石子合并问题

一般来说，有下面几种转换方法：

  1. 把环变成链，枚举那个缺口，时间复杂度$O(n ^ 4)$；
  2. 考虑到变成环之后，问题转换为求$n$条链上的石子合并问题，那么可以把长度为$n$的链拆开，复制一次，变成长度为$2n$的链，用石子合并的方法求出$f_{i, j}$后，求出$\min(f_{i, i + n - 1})$，时间复杂度$O(8n ^ 3)$；

显然第二种更好。

洛谷-P1880-[NOI1995] 石子合并

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
#include <iostream>

const int N = 205, PosInf = 1e9;

int n;
int a[N], s[N], f[N][N], g[N][N];

int main()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            if (i == j)
                f[i][i] = g[i][i] = 0;
            else
            {
                f[i][j] = PosInf;
                g[i][j] = -PosInf;
            }
        }

    std::cin >> n;
    for (int i = 1; i <= n; i++)
    {
        std::cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 1; i <= n * 2; i++)
        s[i] = s[i - 1] + a[i];

    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= n * 2; l++)
        {
            int r = l + len - 1;
            for (int k = l; k < r; k++)
            {
                f[l][r] = std::min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                g[l][r] = std::max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
            }
        }

    int wMin = PosInf, wMax = -PosInf;
    for (int l = 1; l <= n; l++)
    {
        wMin = std::min(wMin, f[l][l + n - 1]);
        wMax = std::max(wMax, g[l][l + n - 1]);
    }
    std::cout << wMin << std::endl;
    std::cout << wMax << std::endl;
    return 0;
}

问题拓展

AcWing-320-能量项链

本题和前面的合并略有不同，待合并的两个区间不是由点构成，而是由点与点之间的空隙构成。因此区间长度至少是3，至多是$n + 1$，且断点$k$不能和左端点相等。

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
#include <iostream>

const int N = 205, PosInf = 1e9;

int n;
int a[N], f[N][N];

int main()
{
    std::cin >> n;
    for (int i = 1; i <= n; i++)
    {
        std::cin >> a[i];
        a[i + n] = a[i];
    }

    for (int len = 3; len <= n + 1; len++)
        for (int l = 1; l + len - 1 <= n * 2; l++)
        {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k++)
                f[l][r] = std::max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
        }

    int wMax = -PosInf;
    for (int l = 1; l <= n; l++)
        wMax = std::max(wMax, f[l][l + n]);
    std::cout << wMax << std::endl;
    return 0;
}

LibreOJ-10149-凸多边形的划分

可以将一个多边形的划分拆为三部分：左，中（三角形），右。最小价值即为这三者的价值和，于是可以发现转移方程和能量项链类似：
$$
f_{i, j} = \min(f_{i, j}, f_{i, k} + f{k, j} + w_i w_k w_j)
$$
注意，本题数据较大，需要做高精度。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstring>

const int N = 55, M = 35, PosInf = 1e9;

int n, w[N];
long long f[N][N][M];

void Add(long long a[], long long b[])
{
    static long long c[M];
    memset(c, 0, sizeof(c));
    for (int i = 0, t = 0; i < M; i++)
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof(c));
}

void Mul(long long a[], long long b)
{
    static long long c[M];
    memset(c, 0, sizeof(c));
    long long t = 0;
    for (int i = 0; i < M; i++)
    {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof(c));
}

int Comp(long long a[], long long b[])
{
    for (int i = M - 1; i >= 0; i--)
        if (a[i] > b[i])
            return 1;
        else if (a[i] < b[i])
            return -1;
    return 0;
}

int main()
{
    std::cin >> n;
    for (int i = 1; i <= n; i++)
        std::cin >> w[i];

    long long temp[M];
    for (int len = 3; len <= n + 1; len++)
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            f[l][r][M - 1] = 1;
            for (int k = l + 1; k < r; k++)
            {
                memset(temp, 0, sizeof(temp));
                temp[0] = w[l];
                Mul(temp, w[k]);
                Mul(temp, w[r]);
                Add(temp, f[l][k]);
                Add(temp, f[k][r]);
                if (Comp(f[l][r], temp) > 0)
                    memcpy(f[l][r], temp, sizeof(temp));
            }
        }

    int k = M - 1;
    while (k > 0 && f[1][n][k] == 0)
        k--;
    for (int i = k; i >= 0; i--)
        std::cout << f[1][n][i];
    std::cout << std::endl;
    return 0;
}

AcWing-479-加分二叉树

这个题乍一看似乎和动态规划没有关系，但我们仔细分析“中序”，可以发现，正如区间中用点分割，中序遍历中，左右子树和根正好可以通过区间型动态规划的经典处理方式划分。因此用$f_{i, j}$表示中序遍历为输入数组的$i$到$j$位的二叉树中加分的最大值，但由于要输出具体方案，还要用$g_{i, j}$表示中序遍历为输入数组的$i$到$j$位的二叉树的根的序号。

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
53
#include <iostream>

const int N = 35;

int n, w[N];
int f[N][N], g[N][N];

void Print(int l, int r)
{
    if (l > r)
        return;

    int root = g[l][r];
    std::cout << root << " ";
    Print(l, root - 1);
    Print(root + 1, r);
}

int main()
{
    std::cin >> n;
    for (int i = 1; i <= n; i++)
        std::cin >> w[i];

    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            if (len == 1)
            {
                f[l][r] = w[l];
                g[l][r] = l;
            }
            else
            {
                for (int k = l; k <= r; k++)
                {
                    int subl = (k == l) ? 1 : f[l][k - 1];
                    int subr = (k == r) ? 1 : f[k + 1][r];
                    int score = subl * subr + w[k];
                    if (f[l][r] < score)
                    {
                        f[l][r] = score;
                        g[l][r] = k;
                    }
                }
            }
        }

    std::cout << f[1][n] << std::endl;
    Print(1, n);
    return 0;
}

DCOJ2008. 蜜雪冰城

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
const int N = 55, M = 4005;
int n, m;
int a[M], b[M], c[M];
int f[N][N][M], g[N][N][M];
vector<int> s;
int cnt[M];
void init(int l, int r, int k)
{
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1;i <= m;i ++)
        if(l <= a[i] && b[i] <= r && a[i] <= k && k <= b[i]) cnt[c[i]] ++;
}
int ba[N][N][M], reba[N][N][M];
void out(int l, int r, int id)
{
    int wh = ba[l][r][id];
    if(l <= wh - 1) out(l, ba[l][r][id] - 1, reba[l][wh - 1][id]);
    printf("%d ", s[id - 1]);
    if(wh + 1 <= r) out(wh + 1, r, reba[wh + 1][r][id]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= m;i ++) cin >> a[i] >> b[i] >> c[i], s.push_back(c[i]);
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    for(int i = 1;i <= m;i ++) c[i] = lower_bound(s.begin(), s.end(), c[i]) - s.begin() + 1;
    for(int l = n;l >= 1;l --)
    {
        for(int r = l;r <= n;r ++)
        {
            for(int k = l, sum;k <= r;k ++)
            {
                init(l, r, k);
                sum = 0;
                for(int i = s.size(), ans;i >= 1;i --)
                {
                    sum += cnt[i];
                    ans = sum * s[i - 1] + g[l][k - 1][i] + g[k + 1][r][i];
                    if(ans > f[l][r][i] || !f[l][r][i])
                    {
                        f[l][r][i] = ans;
                        ba[l][r][i] = k;
                    }
                }
            }
            for(int k = s.size();k >= 1;k --)
            {
                if(f[l][r][k] > g[l][r][k + 1] || !g[l][r][k + 1])
                {
                    g[l][r][k] = f[l][r][k];
                    reba[l][r][k] = k;
                }
                else {
                    g[l][r][k] = g[l][r][k + 1];
                    reba[l][r][k] = reba[l][r][k + 1];
                }
            }
        }
    }
    printf("%d\n", g[1][n][1]);
    out(1, n, reba[1][n][1]);
    return 0;
}

AcWing-321-棋盘分割

先来一波推导。
$$
ans^2=\dfrac{\sum_{i=1}^{n}(x_i -\overline x)}{n}\ =\dfrac1n(\sum_{i=1}^n(x_i^2-2x_i\overline x+\overline x^2))
$$

$$
=\dfrac1n(\sum_{i=1}^nx_i^2-2\overline x\sum_{i=1}^nx_i+n \overline x^2)
$$

$$
=\dfrac {\sum_{i=1}^nx_i^2}n-\overline x^2
$$

本题的划分分为横向和纵向，同时区间也由一维扩展到了二维，因此实现时可以用记忆化搜索的方式减少代码量。用$f_{x1, y1, x2, y2, k}$表示$(x1, y1)$到$(x2, y2)$这个二维区间分割$k$次的最小均方差，那么这个区间可以横向或纵向划分，且可以任意选取划分后的两个子区间，按照这个逻辑，可以写出下面的代码：

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
53
54
55
56
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>

const int m = 8, M = 9, N = 20, PosInf = 1e9;

int n, s[M][M];
double f[M][M][M][M][N];
double average;

inline double Calc(int x1, int y1, int x2, int y2)
{
    double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
    return (sum - average) * (sum - average) / n;
}

inline double Search(int x1, int y1, int x2, int y2, int k)
{
    double &v = f[x1][y1][x2][y2][k];
    if (v >= 0)
        return v;
    if (k == 1)
        return v = Calc(x1, y1, x2, y2);

    v = PosInf;
    for (int i = x1; i < x2; i++)
    {
        v = std::min(v, Search(x1, y1, i, y2, k - 1) + Calc(i + 1, y1, x2, y2));
        v = std::min(v, Search(i + 1, y1, x2, y2, k - 1) + Calc(x1, y1, i, y2));
    }
    for (int i = y1; i < y2; i++)
    {
        v = std::min(v, Search(x1, y1, x2, i, k - 1) + Calc(x1, i + 1, x2, y2));
        v = std::min(v, Search(x1, i + 1, x2, y2, k - 1) + Calc(x1, y1, x2, i));
    }

    return v;
}

int main()
{
    std::cin >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
        {
            std::cin >> s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }

    memset(f, -1, sizeof(f));
    average = (double)s[m][m] / n;

    std::cout << std::fixed << std::setprecision(3) << sqrt(Search(1, 1, 8, 8, n)) << std::endl;
    return 0;
}

洛谷-P1436-棋盘分割

这个跟上面一题其实是一样的，经过数学推导，上题求均方差，也就是求平方和，但均方差可以直接求。

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 <iostream>
#include <cstring>

const int m = 8, M = 9, N = 20, PosInf = 1e9;

int n, s[M][M];
double f[M][M][M][M][N];

int Calc(int x1, int y1, int x2, int y2)
{
    double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
    return sum * sum;
}

double Search(int x1, int y1, int x2, int y2, int k)
{
    double &v = f[x1][y1][x2][y2][k];
    if (v >= 0)
        return v;
    if (k == 1)
        return v = Calc(x1, y1, x2, y2);

    v = PosInf;
    for (int i = x1; i < x2; i++)
    {
        v = std::min(v, Search(x1, y1, i, y2, k - 1) + Calc(i + 1, y1, x2, y2));
        v = std::min(v, Search(i + 1, y1, x2, y2, k - 1) + Calc(x1, y1, i, y2));
    }
    for (int i = y1; i < y2; i++)
    {
        v = std::min(v, Search(x1, y1, x2, i, k - 1) + Calc(x1, i + 1, x2, y2));
        v = std::min(v, Search(x1, i + 1, x2, y2, k - 1) + Calc(x1, y1, x2, i));
    }

    return v;
}

int main()
{
    std::cin >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
        {
            std::cin >> s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }

    memset(f, -1, sizeof(f));

    std::cout << Search(1, 1, 8, 8, n) << std::endl;
    return 0;
}

区间型动态规划的两种实现方式

迭代式（推荐）

1
2
3
4
5
6
7
for (int len = 1; len <= n; len++)
    for (int l = 1; l + len - 1 <= n; l++)
    {
        r = l + len - 1;
        for (int k = l; k < r; k++)
            // do something
    }

记忆化搜索式（适合状态定义较为复杂的情况）

如果状态定义中数组维数太多，需要些很多重循环，这时可以用记忆化搜索的形式来写。

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

$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;
}