讲课，ps

什么是区间dp

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

石子合并问题

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

以最小值为例，对于这个问题，如果我们用 $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 \leq k < j)$
初始值：
$f_{i, i} = 0$
时间复杂度 $O (n^{3})$ 。

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

环形石子合并问题

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

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

显然第二种更好。

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

#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$ 不能和左端点相等。

#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})$
注意，本题数据较大，需要做高精度。

#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$ 位的二叉树的根的序号。

#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. 蜜雪冰城

#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-棋盘分割

先来一波推导。
$a n s^{2} = \frac{\sum_{i = 1}^{n} (x_{i} - \overset{―}{x})}{n} = \frac{1}{n} (\sum_{i = 1}^{n} (x_{i}^{2} - 2 x_{i} \overset{―}{x} + {\overset{―}{x}}^{2}))$

$= \frac{1}{n} (\sum_{i = 1}^{n} x_{i}^{2} - 2 \overset{―}{x} \sum_{i = 1}^{n} x_{i} + n {\overset{―}{x}}^{2})$

$= \frac{\sum_{i = 1}^{n} x_{i}^{2}}{n} - {\overset{―}{x}}^{2}$

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

#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-棋盘分割

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

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

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

迭代式（推荐）

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 的四边形不等式优化

$2 D / 1 D$ $d p$ 的方程模型如下：
$d [i, j] = min_{l (i, j) \leq k \leq r (k, j)} (d [i, k] + d [k + 1, j] + v a l (i, j))$

其中 $2 D$ 指枚举的状态数， $1 D$ 指枚举的决策数，最典型的是区间 $d p$ ，明显，直接 $d p$ 时间为 $O (n^{3})$ （一定要注意 $v a l (i, j)$ 与 $k$ 无关）

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

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

对于 $2 D / 1 D$ $d p$ 的方程：
$d [i, j] = min_{l (i, j) \leq k \leq r (k, j)} (d [i, k] + d [k + 1, j] + v a l (i, j))$
若 $v a l$ 满足四边形不等式和区间包含单调性， $d$ 满足 $d [i, i] = v a l (i, i) = 0$ ，且 $i \leq l (i, j) \leq 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 \leq l (i, j) \leq r (i, j) < j$ ， $d [i, i + 2]$ 的决策最多只有 $i$ 和 $i + 1$

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

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

由于 $v a l$ 满足四边形不等式，有 $v a l (i, i + 1) + v a l (i, i + 2) \geq v a l (i, i + 1) + v a l (i + 1, i + 2)$

故 $d [i, j + 1] + d [i + 1, j] \geq d [i, j] + d [i + 1, j + 1]$ ，即 $d$ 满足四边形不等式
若 $d [i, i + 2]$ 的最优决策为 $i$ ，同理有
$d [i, i + 2] = d [i, i] + d [i + 1, i + 2] + v a l (i, i + 2) = d [i + 1, i + 2] + v a l (i, i + 2) = v a l (i + 1, i + 2) + v a l (i, i + 2)$
$d [i + 1, i + 2] + d [i, i + 1] = v a l (i + 1, i + 2) + v a l (i, i + 1) = d [i + 1, j + 1] + d [i, j]$

同样由 $v a l$ 满足四边形不等式，得 $d [i, j + 1] + d [i + 1, j] \geq 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] + v a l (i, j + 1) + d [i + 1, y] + d [y + 1, j] + v a l (i + 1, j)$
而对于 $d [i, j]$ 和 $d [i + 1, j + 1]$ ， $x, y$ 就不一定是最优决策了

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

当 $x \geq 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) \leq k \leq r (k, j)} (d [i, k] + d [k + 1, j] + v a l (i, j))$
记 $d [i, j]$ 的最优决策点为 $b p [i, j]$ ，若 $\forall i < j$ 有 $b p [i, j - 1] \leq b p [i, j] \leq b p [i + 1, j]$ ，则称 $d$ 具有决策单调性

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

证明：

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

QED

实现

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

时间也很好分析：
$\begin{aligned} \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} (b p [i + 1, j] - b p [i, j - 1] + 1) \\ = & \sum_{i = 1}^{n - 1} (b p [i + 1, n] - b p [1, n - i] + n - i) \\ \leq & 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})$ 已经是最好复杂度了）

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

例题十一

一个古老的石头游戏

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

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

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

思路

呃呃，还要思路吗？

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

代码

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