DP 学习笔记（三）：与斜率有关的 DP 优化

· · 算法·理论

几何无王者之道，惟有点与线之舞蹈。————笛卡尔

几何不光只有中考高考考的那三瓜两枣，在 DP 中也可以有非常重要的作用。

基础知识

斜率

函数的凹凸性

凸壳

斜率优化

这种优化算是后面要讲的决策单调性的特殊情况，不过没有决策单调性的性质也可以做。

P2900 [USACO08MAR] Land Acquisition G

P4360 [CEOI 2004] 锯木厂选址

P3628 [APIO2010] 特别行动队

四边形不等式优化

应用场合

对于区间 DP，我们一般需要枚举一段区间的分割点，把当前区间拆分成两个小区间，把两个小区间的答案加起来再加上这两个区间合在一起的代价，也就是 dp_{i, j} = \displaystyle\min_{k = i}^{j - 1} dp_{i, k} + dp_{k + 1, j} + w_{i, j}（\max 也是一样的），朴素做法的时间复杂度是 O(n^3)，但是如果 w_{i, j} 满足一些性质，那么我们可以将其优化到 O(n^2)（对于 DP 来说已经是一个非常好的复杂度了）。

四边形不等式的定义

我们先给出四边形不等式的定义：设 w 是定义在整数集合上的二元函数，对于任意整数 i \leq i' \leq j \leq j'，如果有 w(i, j) + w(i', j') \leq w(i, j') + w(i', j)（也就是交叉的两个区间大于包含的两个区间），就称 w 满足四边形不等式。

为什么这个叫做四边形不等式，我们考虑将这四个区间画在数轴上：

我们把 i' 和 j' 提到一个更高的水平线上，再把每条线拉直，此时我们就能得到一个梯形：

此时我们要证明 AC + BD \geq AD + BC，以下是它的证明：

在 \triangle AOD 中，运用三角形两边之和大于第三边，可以得到 AO + OD \geq AD，同理，BO + OC \geq BC，将等式左边相加，右边也相加，就可以得到 AO + BO + OC + OD \geq AD + BC，即 AC + BD \geq AD + BC。你会发现这个式子和 w 满足的不等式正好相反，因此信息中的四边形不等式可以理解成几何中的反四边形不等式。而当你把这个四边形两个点缩成一个时，w 又满足反三角不等式，即两边之和小于第三边。

下面再给出二元函数单调性的定义：如果对于任意整数 i \leq i' \leq j \leq j'，有 w(i, j') \geq w(i', j)，则称 w 具有单调性，也就是大区间的权值大于小区间的权值。

四边形不等式定理

我们先来一些定义，我们设二元函数 c 满足：

\begin{cases} c(i, i) = 0\\ c(i, j) = w(i, j) + \displaystyle\min_{k = i}^{j - 1} c_{i, k} + c_{k + 1, j} \end{cases}

这个 c 和之前的 DP 函数很像，就是把 w(i, j) 提到了外面去，其实本质是一样的。

这里的二元函数 w 也是有限制的，需要满足四边形不等式和单调性，即：

\begin{cases} w(i, j) + w(i', j') \leq w(i', j) + w(i, j')\\ w(i', j) \leq w(i, j') \end{cases} (i \leq i' \leq j \leq j')

下面，我们先来证明两个引理。

引理 2.3.1

如果 w 满足四边形不等式和单调性，那么 c 也满足四边形不等式，即 c(i, j) + c(i', j') \leq c(i', j) + c(i, j'), i \leq i' \leq j \leq j'。

证明：

分以下 3 种情况讨论：

现在就证明了引理 2.3.1。

引理 2.3.2

用 K_c(i, j) 表示使 c(i, j) 得到最小值的那些 k 中，最大的那个，那么引理 2.3.2 可以表示成 K_c(i, j) \leq K_c(i, j + 1) \leq K_c(i + 1, j + 1)。

证明：

当 i = j 时显然成立，考虑 i < j 的这种情况。

我们先证明 K_c(i, j) \leq K_c(i, j + 1)。这就相当于证明对于 i < k \leq k' \leq j，若 c_{k'}(i, j) \leq c_k(i, j)，则 c_{k'}(i, j + 1) \leq c_k(i, j + 1)，也就是说，如果在 [i, j] 这个区间内，存在比 k 更大的最优分割点 k'，那么当拓展到区间 [i, j + 1] 时，依然有 c_{k'}(i, j + 1) \geq c_k(i, j + 1)，那么 k 就一定不是区间 [i, j + 1] 的最大的最优分割点，k' 有可能是区间 [i, j + 1] 的最大的最优分割点，但由于 k' 已经大于 k，如果有更优的分割点，那它一定比 k 大了，此时就等价于 K_c(i, j) \leq K_c(i, j + 1)。

根据引理 2.3.1 的结论，若 k \leq k' \leq j < j + 1，则有 c(k, j) + c(k', j + 1) \leq c(k', j) + c(k, j + 1)。

我们把不等式两边同时加上 w(i, j) + w(i, j + 1) + c(i, k) + c(i, k')，根据 c 的定义式，有 c_k(i, j) + c_{k'}(i, j + 1) \leq c_{k'}(i, j) + c_k(i, j + 1)，于是 c_{k'}(i, j + 1) \leq c_{k'}(i, j) + c_k(i, j + 1) - c_k(i, j)。

由于我们有 c_{k'}(i, j) \leq c_k(i, j)，我们将不等式两边同时加上 c_k(i, j + 1)，再移项，可以得到 c_{k'}(i, j) + c_k(i, j + 1) - c_k(i, j) \leq c_k(i, j + 1)，对比上一个等式，就可以得到 c_{k'}(i + 1, j) \leq c_k(i, j + 1)，那么此时我们就证明了引理 2.3.2。

定理 2.3.1（四边形不等式定理）

现在开始证明最主要的这个定理了。

四边形不等式定理的内容是，用 DP 计算所有 c(i, j) 的时间复杂度为 O(n^2)。

证明：

我们计算区间 DP 时，一般都是枚举区间长度，再枚举左端点，也就是按照 len = 1, 2, \dots n 的顺序进行枚举。当我们把 DP 从 c(i, j) 转移到 c(i, j + 1) 时，由于引理 2.3.2 的限制，只需要 K_c(i + 1, j + 1) - K_c(i, j) 次，就可以完成所有转移，那我们把 i 取所有值的情况都求出来：

\begin{cases} i = 1, K_c(1 + 1, 1 + len + 1) - K_c(1, len + 1) = K_c(2, len + 2) - K_c(1, len + 1)\\ i = 2, K_c(2 + 1, 2 + len + 1) - K_c(2, len + 2) = K_c(3, len + 3) - K_c(2, len + 2)\\ i = 3, K_c(3 + 1, 3 + len + 1) - K_c(3, len + 3) = K_c(4, len + 4) - K_c(3, len + 3)\\ \dots\\ i = n - len, K_c(n - len + 1, n - len + len + 1) - K_c(n - len, len + n - len) = K_c(n - len + 1, len + 1) - K_c(n - len, len) \end{cases}

将等式左边加在一起，右边加在一起，那么总枚举次数就是 K_c(n - len + 1, n + 1) - K_c(1, len + 1) < n = O(n)，一共有 O(n) 种不同的 len，因此总时间复杂度就是 O(n^2)，完成了证明。

当求的东西从 \min 变成了 max，只用将 w 满足的两个不等式的 \leq 改成 \geq 就可以了。

应用

其实在真正的比赛中，一般都是打表发现单调性与四边形不等式就直接用了，但在此处还是证明一下吧。

P1880 [NOI1995] 石子合并

这道题目在区间 DP 时已经讲过了，但是可以用四边形不等式进一步优化成 O(n^2)。

我们已知它的 DP 转移方程是 dp_{i, j} = \displaystyle\min_{k = i + 1}^{j - 1} dp_{i, k - 1} + dp_{k + 1, j} + sum_{i, j}（sum 为 i 到 j 的石子数之和），很显然，因为每个石子堆石子数都是非负的，那么 sum_{i, j} 一定满足单调性，而在这个题中 sum_{i, j'} + sum_{i', j} = sum_{i, j} + sum_{i', j'}，也满足四边形不等式，因此可以用四边形不等式定理优化成 O(n^2)。

但是我们要求最大值时，发现 sum_{i, j} 不满足大区间的权值小于小区间的权值，因此无法用四边形不等式优化，但是最大值有一个性质，那就是只会从转移区间的两个端点处转移（不想证明了），那么最大值只有考虑两个端点的 DP 值哪个更大就可以了。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 9;
int n, a[N], dp[N][N], dp2[N][N], s[N][N], num[N], ans1 = 100000000, ans2 = 0;
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        num[i] = num[i - 1] + a[i];
    }
    for(int i = 1; i <= n - 1; i++)
        num[i + n] = num[i + n - 1] + a[i];
    n = n * 2 - 1;
    for(int i = 1; i <= n; i++)
        s[i][i] = i;
    for(int len = 2; len <= n; len++){
        for(int i = 1; i <= n - len + 1; i++){
            int j = i + len - 1;
            dp[i][j] = 100000000;
            for(int k = s[i][j - 1]; k <= s[i + 1][j]; k++)
                if(dp[i][k] + dp[k + 1][j] + num[j] - num[i - 1] < dp[i][j]){
                    dp[i][j] = dp[i][k] + dp[k + 1][j] + num[j] - num[i - 1];
                    s[i][j] = k;
                }
            dp2[i][j] = max(dp2[i][j - 1], dp2[i + 1][j]) + num[j] - num[i - 1];
        }
    }
    n = (n + 1) / 2;
    for(int i = 1; i <= n; i++){
        ans1 = min(ans1, dp[i][n + i - 1]);
        ans2 = max(ans2, dp2[i][n + i - 1]); 
    }
    printf("%d\n%d", ans1, ans2);
    return 0;
}

UVA10304 Optimal Binary Search Tree

这就是四边形不等式优化的来源。

其实这道题目和石子合并特别像，如果我们把合并过程看成一棵树，那么每堆石子的贡献就是石子的个数乘以这堆石子的深度，因此我们有类似的 DP 优化方法。

我们设 dp_{i, j} 为把 i 到 j 的数字建成二叉搜索树的权值最小值。首先根据二叉搜索树的性质，每个节点左儿子的权值总是小于右儿子的，而且这道题目还把权值排好了序，那么显然，我们要在 [i, j] 找到一个 k 作为根，那么此时左右子树所有节点的深度全部加上了 1，因此总权值就增加了 sum_{i, j} - e_k，因此转移方程就是 dp_{i, j} = \displaystyle\min_{k = i}^{j - 1} dp_{i, k} + dp_{k + 1, j} + sum_{i, j} - e_k，它的单调性和四边形不等关系和上一题证法类似，可以优化成 O(n^2)。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 259;
int dp[N][N], s[N][N], sum[N], a[N], n;
signed main(){
    while(~scanf("%lld", &n) && n){
        memset(s, 0, sizeof(s));
        memset(dp, 0x3f, sizeof(dp));
        for(int i = 1; i <= n; i++){
            scanf("%lld", &a[i]);
            sum[i] = sum[i - 1] + a[i];
            s[i][i] = i;
            dp[i][i] = dp[i + 1][i] = dp[i][i - 1] = 0;
        }
        for(int len = 2; len <= n; len++){
            for(int i = 1; i + len - 1 <= n; i++){
                int j = i + len - 1;
                for(int k = s[i][j - 1]; k <= s[i + 1][j]; k++){
                    if(dp[i][j] > dp[i][k - 1] + dp[k + 1][j] + sum[j] - sum[i - 1] - a[k]){
                        dp[i][j] = dp[i][k - 1] + dp[k + 1][j] + sum[j] - sum[i - 1] - a[k];
                        s[i][j] = k;
                    }
                }
            }
        }
        printf("%lld\n", dp[1][n]);
    }
    return 0;
}

P4767 [IOI 2000] 邮局 加强版

为什么是先出加强版再出普通版？？？？

我们设 dp_{i, j} 表示前 i 个村庄一共有 j 个邮局的最小距离和，和区间 DP 一样，我们考虑将其划分成两个小区间 [1, k] 和 [k + j, j]（至于为什么不能区间 DP，可以发现复杂度是 O(n^3)，无法通过），在第 1 个区间内放 j - 1 个邮局，在第 2 个区间内放剩下的 1 个邮局，转移方程是 dp_{i, j} = \displaystyle\min_{k = j - 1}^n dp_{k, j - 1} + w_{k + 1, i}（其中 w_{i, j} 为 [i, j] 的村庄内放 1 个邮局，[i, j] 内所有村庄到邮局距离和的最小值），根据初中知识，我们知道如果村庄个数为奇数，那么就把邮局安排在最中间的村庄，否则就安排在中间两个村庄中的任意一个，可以很好预处理出。

现在我们来分析 w_{i, j} 这个函数。我们此时要证明 w_{i, j'} + w_{i', j} \leq w_{i', j'} + w_{i, j} 。其实四边形不等式定理还有一个等价命题，那就是若对于 i < i + 1 \leq j < j + 1，有 w_{i, j} + w_{i + 1, j + 1} \leq w_{i, j + 1} + w_{i + 1, j}，那么称 w 满足四边形不等式。因此我们考虑 w_{i, j} 与 w_{i, j - 1} 的关系，由于邮局总是处于中间位置，那么有 w_{i, j} = w_{i, j - 1} + a_j - a_{\lfloor\frac{i + j}{2}\rfloor}，那么 w_{i, j + 1} - w_{i, j} = a_{j + 1} - a_{\lfloor\frac{i + j + 1}{2}\rfloor}，而 w_{i + 1, j + 1} - w_{i + 1, j} = a_{j + 1} - a_{\lfloor\frac{i + j + 2}{2}\rfloor}，两式相减可以得到 w_{i, j + 1} + w_{i + 1, j} - w_{i, j} - w_{i + 1, j + 1} = a_{\lfloor\frac{i + j + 2}{2}\rfloor} - a_{\lfloor\frac{i + j + 1}{2}\rfloor}，由于所给的 a 是单增的，因此这个值一定大于 0，因此 w_{i, j} + w_{i + 1, j + 1} \geq w_{i, j + 1} + w_{i + 1, j}，满足四边形不等式。而根据 w_{i, j} 的递推式，一定是大区间的权值大于小区间的权值，因此可以通过四边形不等式优化。

由于本题不是一般的区间 DP，我们求 dp_{i, j} 要用到 dp_{i + 1, j} 的最优分割点，因此 i 这一维需要倒序枚举。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e2 + 9, M = 3e3 + 9;
int a[M], dis[M][M], f[M][N], s[M][N], n, m;
signed main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i++){
        dis[i][i] = 0;
        for(int j = i + 1; j <= n; j++)
            dis[i][j] = dis[i][j - 1] + a[j] - a[(i + j) >> 1];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for(int j = 1; j <= m; j++){
        s[n + 1][j] = n;
        for(int i = n; i >= 1; i--)
            for(int k = s[i][j - 1]; k <= s[i + 1][j]; k++)
                if(f[i][j] > f[k][j - 1] + dis[k + 1][i]){
                    f[i][j] = f[k][j - 1] + dis[k + 1][i];
                    s[i][j] = k;
                }
    }   
    printf("%lld", f[n][m]);
    return 0;
}

P4072 [SDOI2016] 征途

这道题目和上一道，都是将 n 个数划分成 m 个区间的问题。

我们设第 i 天走的路程为 v_i，考虑方差的计算公式 s^2 = \displaystyle\frac{\sum\limits_{i = 1}^m (\overline v - v_i)^2}{m} = \frac{\sum\limits_{i = 1}^m \left(\frac{\sum\limits_{i = 1}^m v_i}{m} - v_i \right)}{m}^2。

将平方展开，可以得到原式

\begin{aligned} &= \displaystyle\frac{\sum\limits_{i = 1}^m \frac{\left(\sum\limits_{i = 1}^m v_i \right)^2}{m^2} - 2 \frac{\sum\limits_{i = 1}^m v_i}{m} v_i + v_i^2}{m} \\&= \frac{m \times \frac{\left(\sum\limits_{i = 1}^m v_i \right)^2}{m^2} - 2 \frac{\sum\limits_{i = 1}^m v_i}{m} (\sum\limits_{i = 1}^m v_i) + \sum\limits_{i = 1}^m v_i^2}{m} \end{aligned}

乘以 m^2 后，可以得到 \left(\displaystyle\sum_{i = 1}^m v_i \right)^2 - 2\left(\displaystyle\sum_{i = 1}^m v_i \right)^2 + m\displaystyle\sum_{i = 1}^m v_i^2 = m\sum_{i = 1}^m v_i^2 - \left(\sum_{i = 1}^m v_i \right)^2。此时我们会发现后一项为定值，于是我们要让前一项尽可能小。

此时我们就可以开始 DP 了，设 dp_{i, j} 表示前 i 段路用 j 天走，每天走的路程的平方和，那我们考虑第 i 天走了多少距离，那么 dp_{i, j} = \displaystyle\min_{k = 1}^i dp_{k, j - 1} + (sum_i - sum_{k - 1})^2。

现在的价值函数变成了 (sum_i - sum_j)^2(j < i)，于是我们现在要证明大区间的权值大于小区间的权值，且交叉优于包含。第一个单调性显然成立，第二个相当于证明 (sum_{i + 1} - sum_j)^2 + (sum_i - sum_{j + 1})^2 \leq (sum_{i + 1} - sum_{j + 1})^2 + (sum_i - sum_j)^2。

将两边的式子拆开，可以得到 sum_{i + 1}sum_j + sum_isum_{j + 1} \leq sum_{i + 1}sum_{j + 1} + sum_isum_j \iff 2sum_isum_j + a_{i + 1} sum_j + a_{j + 1} sum_i \leq 2sum_isum_j + a_{i + 1} sum_j + a_{j + 1} sum_i + a_{i + 1} a_{j + 1}，那么可以得到 a_{i + 1}a_{j + 1} \geq 0，这是显然成立的，那么四边形不等式证明成立。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e3 + 2;
int a[N], sum[N], f[N][N], s[N][N], n, m;
signed main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for(int j = 1; j <= m; j++){
        s[n + 1][j] = n;
        for(int i = n; i >= 1; i--)
            for(int k = s[i][j - 1]; k <= s[i + 1][j]; k++)
                if(f[i][j] > f[k][j - 1] + (sum[i] - sum[k]) * (sum[i] - sum[k])){
                    f[i][j] = f[k][j - 1] + (sum[i] - sum[k]) * (sum[i] - sum[k]);
                    s[i][j] = k;
                }
    }   
    printf("%lld", f[n][m] * m - sum[n] * sum[n]);
    return 0;
}

拓展：\text{Garsia-Wachs} 算法

P5569 [SDOI2008] 石子合并

决策单调性优化

DP 也是一种数据结构，它维护了数组。———— hfu

这在决策单调性中很有体现。

应用场合

其实，我们之前做P4767 [IOI 2000] 邮局 加强版时已经发现它不再是标准的区间 DP 了，如果去掉邮局的个数限制，那么这道题就变成了一维的 DP。当 n 比较大时，已经存不了区间决策点了，也只能用一维 DP。其实一维的 DP 也可以用四边形不等式优化，不过此时它就叫做决策单调性优化。

对于形如 dp_i = \displaystyle\min_{j = 0}^{i - 1} dp_j + w_{j, i} 的 DP 转移方程，我们设 p_i 是使 dp_j + w_{j, i} 取得最小值的 j，即 j 是 i 的最优决策点，那么如果 w_{i, j} 满足四边形不等式，即 w_{i, j'} + w_{i', j} \geq w_{i, j} + w_{i', j'}，那么 p_i 是单调不降的。

证明：

对于 i \in [i, n], j \in [0, p_i - 1]，根据 p_i 的定义，有 dp_{p_i} + w_{p_i, i} \leq dp_j + w_{j, i}。而对于 i' \in [i + 1, n]，由于 w 满足四边形不等式，那么 w_{j, i'} + w_{p_i, i} \geq w_{j, i} + w_{p_i, i'}，移项可以得到 w_{p_i, i'} - w_{p_i, i} \leq w_{j, i'} - w_{j, i}，将这个不等式加上 dp_{p_i} + w_{p_i, i} \leq dp_j + w_{j, i}，最终可以得到 dp_{p_i} + w_{p_i, i'} \leq dp_j + w_{j, i'}，这也就是说，小于 p_i 的决策点，肯定不会成为 i' 的决策点，那么 p_{i'} 一定 \geq p_i，那么决策点就是单调不降的了。

另一种决策单调性：对于形如 dp_i = \displaystyle\max_{j = 0}^{i - 1} dp_j + w_{j, i} 的 DP 转移方程，如果 w_{i, j} 满足四边形不等式，即 w_{i, j'} + w_{i', j} \geq w_{i, j} + w_{i', j'}，那么 p_i 是单调不升的。

证明：

对于 i \in [i, n], j \in [p_i + 1, i - 1]，根据 p_i 的定义，有 dp_{p_i} + w_{p_i, i} \geq dp_j + w_{j, i}。而对于 i' \in [i + 1, n]，由于 w 满足四边形不等式，那么 w_{j, i} + w_{p_i, i'} \geq w_{j, i'} + w_{p_i, i}，移项可以得到 w_{p_i, i'} - w_{p_i, i} \geq w_{j, i'} - w_{j, i}，将这个不等式加上 dp_{p_i} + w_{p_i, i} \geq dp_j + w_{j, i}，最终可以得到 dp_{p_i} + w_{p_i, i'} \geq dp_j + w_{j, i'}，这也就是说，大于 p_i 的决策点，肯定不会成为 i' 的决策点，那么 p_{i'} 一定 \leq p_i，那么决策点就是单调不升的了。

应用

运用决策单调性可以把形如 dp_i = \displaystyle\min_{j = 0}^{i - 1} dp_j + w_{j, i} 或 dp_i = \displaystyle\min_{j = 0}^{i - 1} f_j + w_{j, i} 的式子从 O(n^2) 优化到 O(n \log n)。

二分队列

此做法适用于价值函数满足交叉优于包含，且求 \min 的 DP，或是价值函数满足包含优于交叉，且求 \max 的 DP。

我们维护一个队列，其中每个元素都是三元组 (l, r, p) 的形式，它表示 dp_l 到 dp_r 的决策点是 p。

我们枚举每个 i。首先我们先计算出这个 i 的 DP 值（如果 i 的决策点可以是 i，那么就先进行后续操作，再计算 dp_i）， 然后我们考虑 i 会成为哪些 i' > i 的决策点，很显然，我们一定会找到一个分界线，在分界线之前 p 数组存储的决策点都比 i 好，之后的都比 i 差。我们只需要比较一下在某一段 (l, r, p)，在 l 处是 p 更优还是 i 更优，如果在 l 处 i 都比 p 优秀，那么直接将这一段丢掉即可。同样，如果在某一段 (l, r, p)，在 r 处 p 都比 i 优秀，那么 i 就无法继续更新了。

不过还有一点，就是分割点可以在某段 [l, r] 中间，此时我们需要二分查找出该点。

此外，如果一个决策点 j 决策的区间 [l, r] 中 r 已经小于 i 了，那么此时 j 已经无法决策 i 和 i 以后的 DP 值了，直接将其从队头弹出，那么剩下的队头这个决策点的决策区间一定包含 i 了，直接转移即可。

P1912 [NOI2009] 诗人小G

白日依山尽，黄河入海流。

欲穷千里目，更上一层楼。————题目样例

我们设 dp_i 表示前 i 句诗排版后的最小不协调值，那我们考虑第 i 句诗这一行有几句诗，也就是考虑上一个换行的地方在哪里。于是我们记 sum_i 表示前 i 句诗的长度和，于是 dp_i = \displaystyle\min_{0 \leq j < i} dp_j + |sum_i - sum_j + i - j - 1 - L|^P（加上 i - j - 1 是因为每句诗之间有空格）。

这又是这种区间划分的形式，由于有 P 次方，不方便用单调队列优化，于是我们考虑决策单调性。

那么现在，我们需要证明 w_{i, j} = |sum_i - sum_j + i - j - 1 - L|^P 满足四边形不等式，也就是 w_{j, i} + w_{j + 1, i + 1} \leq w_{j, i + 1} + w_{j + 1, i}。我们设 u = (sum_i + i) - (sum_j + j) - (L + 1), v = (sum_i + 1) - (sum_{j + 1} + j + 1) - (L + 1)，那么 w_{j, i + 1} = |sum_i - sum_{j + 1} + (i - j - 2) - L|^P = |v|^P，同理可得 w_{j + 1, i + 1} = |v + (a_{i + 1} + 1)|^P, w_{j, i} = |u|^2, w_{j, i + 1} = |u + (a_{i + 1} + 1)|^P，那么将原式移项后，最终要证明 |v|^P - |v + a_{i + 1} + 1|^P \geq |u|^P - |u + a_{i + 1} + 1|^P。

观察两边式子的形式，可以用 y = |x|^P - |x + C|^P 来刻画这个不等式，由于 sum_{j + 1} \geq sum_j，v 比 u 还多减了一个 1，那么 u 一定大于 v，因此我们需要证明这个函数在 C > 0 时单调不升。

由于含有绝对值，因此我们用零点分段法来证明：

此时我们证明了该函数单调递减，从而证明了四边形不等式。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e6 + 5, INF = 1e18;
int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') 
            f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
struct Node{
    int l, r, pos;
} q[N];
int s[N], pre[N], n, L, k, T, head, tail;
char poem[N][31];
bool flag[N];
long double dp[N];
long double qpow(long double a, int b){
    long double res = 1;
    while(b > 0){
        if(b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
long double w(int j, int i){
    return dp[j] + qpow(abs(s[i] - s[j] + i - j - 1 - L), k);
}
int bs(int id, int x){
    int res = q[id].r, l = q[id].l, r = q[id].r;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(w(q[id].pos, mid) >= w(x, mid)){
            res = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    return res;
}
void insert(int i){
    if(head <= tail && q[head].r < i)
        head++;
    else
        q[head].l = i;
    if(dp[i] > w(q[head].pos, i)){
        dp[i] = w(q[head].pos, i);
        pre[i] = q[head].pos;
    }
    while(head <= tail && w(i, q[tail].l) <= w(q[tail].pos, q[tail].l))
        tail--;
    if(head > tail)
        q[++tail] = Node{i, n, i};
    else if(w(i, q[tail].r) >= w(q[tail].pos, q[tail].r)){
        if(q[tail].r == n)
            return;
        q[tail + 1] = Node{q[tail].r + 1, n, i};
        tail++;
    } else {
        int p = bs(tail, i);
        q[tail].r = p - 1;
        q[++tail] = Node{p, n, i};
    }
}
signed main(){
    T = read();
    while(T--){
        for(int i = 1; i <= n; i++){
            dp[i] = 0;
            pre[i] = 0;
            flag[i] = 0;
        }
        for(int i = 1; i <= tail; i++)
            q[i] = Node{0, 0, 0};
        n = read();
        L = read();
        k = read();
        for(int i = 1; i <= n; i++){
            scanf("%s", poem[i]);
            s[i] = s[i - 1] + strlen(poem[i]);
            dp[i] = w(0, i);
        }
        head = 1;
        tail = 0;
        for(int i = 1; i <= n; i++)
            insert(i);
        if(dp[n] > 1e18)
            printf("Too hard to arrange\n");
        else {
            printf("%.0Lf\n", dp[n]);
            for(int i = n; i; i = pre[i])
                flag[i] = true;
            for(int i = 1; i <= n; i++){
                printf("%s", poem[i]);
                if(flag[i])
                    printf("\n");
                else
                    printf(" ");
            }
        }
        printf("--------------------\n");
    }
    return 0;
}

P3515 [POI 2011] Lightning Conductor

我们设 dp_i 表示在第 i 个建筑物上修建避雷针的最小高度，由于避雷针必须保护所有建筑物，那么答案就必须取保护每一个建筑物的避雷针最小高度的最大值，于是 dp_i = \displaystyle\max_{j = 1}^n h_j - h_i + \sqrt{|i - j|}，其中绝对值可以通过正着扫一遍，倒着扫一遍去掉，于是 dp_i = \displaystyle\max_{j = 1}^i h_j - h_i + \sqrt{i - j} = \max_{j = 1}^i (h_j + \sqrt{i - j}) - h_i。我们此时可以认为 j 为 dp_i 的决策点，于是价值函数就变成了 \sqrt{i - j}。

我们现在要证明 \sqrt{i - j} 满足包含优于交叉，也就是 \sqrt{i - (j + 1)} + \sqrt{(i + 1) - j} \leq \sqrt{i - j} + \sqrt{(i + 1) - (j + 1)}。我们设 i - j = x，于是原式就变成了 2 \sqrt x \geq \sqrt{x + 1} + \sqrt{x - 1}，移项后变成 \sqrt{x + 1} - \sqrt x \leq \sqrt x - \sqrt{x - 1}，现在我们要证明的就是这个式子。

我们构造函数 y = \sqrt{x + 1} - \sqrt x，对它求导可以得到 y = \displaystyle\frac 12 (x + 1)^{-\frac 12} - \frac 12 x^{-\frac 12}，由于 x + 1 > x，那么 (x + 1)^{-\frac 12} < x^{-\frac 12}，于是导函数是个减函数，且斜率恒为负，因此原函数就是一个减函数，因此 \sqrt{x + 1} - \sqrt x \leq \sqrt x - \sqrt{x - 1}，满足四边形不等式。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9;
struct Node{
    int l, r, pos;
} q[N];
int h[N], n, head, tail;
double dp[N];
double w(int j, int i){
    return h[j] + sqrt((i - j) * 1.0);
}
int bs(int id, int x){
    int res = q[id].r + 1, l = q[id].l, r = q[id].r;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(w(q[id].pos, mid) <= w(x, mid)){
            res = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    return res;
}
void insert(int i){
    if(head <= tail && q[head].r < i)
        head++;
    else
        q[head].l = i;
    dp[i] = max(dp[i], w(q[head].pos, i));
    while(head <= tail && w(i, q[tail].l) >= w(q[tail].pos, q[tail].l))
        tail--;
    if(head > tail)
        q[++tail] = Node{i, n, i};
    else if(w(i, q[tail].r) <= w(q[tail].pos, q[tail].r)){
        if(q[tail].r == n)
            return;
        q[tail + 1] = Node{q[tail].r + 1, n, i};
        tail++;
    } else {
        int p = bs(tail, i);
        q[tail].r = p - 1;
        q[++tail] = Node{p, n, i};
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &h[i]);
        dp[i] = h[i];
    }   
    head = 1;
    tail = 0;
    for(int i = 1; i <= n; i++)
        insert(i);  
    for(int i = 1; i <= n / 2; i++){
        swap(h[i], h[n - i + 1]);
        swap(dp[i], dp[n - i + 1]);
    }
    head = 1;
    tail = 0;
    for(int i = 1; i <= n; i++)
        insert(i);
    for(int i = n; i >= 1; i--)
        printf("%d\n", int(ceil(dp[i]) - h[i]));
    return 0;
}

二分栈

此做法适用于价值函数满足交叉大于包含，且求 \max 的 DP，或是价值函数满足包含大于交叉，且求 \min 的 DP。

和二分队列很像，只是这次我们维护的是栈，因为栈满足先进后出，那么越先进入的点就越有可能成为越后进入的点的决策点。

我们依然枚举每个 i，只是这次，如果要替换一整段 (l, r, p)，我们要比较在 r 处谁更优，如果一整段都无法被替换，我们要比较在 l 处谁更优。二分的符号也要反一下，其它就和二分队列一摸一样了。

P5504 [JSOI2011] 柠檬

我们设 dp_i 表示以 i 结尾，把 [1, i] 所有贝壳都变成柠檬，柠檬个数的最大值。首先粗略估计一下 i 的决策点，发现它一定与 i 的大小相同，这是因为如果你多往左选一个，此时变出来的柠檬个数没有变化，还减少了之前一段决策的方案，不会增加柠檬数，于是从与 i 大小相同的地方转移一定不劣，于是我们可以写出以下转移方程：dp_i = \displaystyle\max_{s_j = s_i} dp_{j - 1} + s_i (rk_i - rk_j + 1)^2（rk_i 表示 i 在所有 s_j = s_i 中的排名）。

于是我们每种颜色分开考虑。此时的价值函数是 s_i (rk_i - rk_j + 1)^2，这又是一个二次函数，而二次函数满足四边形不等式的证明，我们已经在P4072 [SDOI2016] 征途给过了，此时我们就可以用二分栈优化了。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9;
struct Node{
    int l, r, pos;
};
vector <int> mp[N];
vector <Node> st[N];
int s[N], dp[N], cnt[N], rk[N], n;
int w(int j, int i, int c){
    return dp[mp[c][j] - 1] + (i - j + 1) * (i - j + 1) * c;
}
int bs(int x, int c){
    int res = st[c].back().l, l = st[c].back().l, r = st[c].back().r;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(w(st[c].back().pos, mid, c) >= w(x, mid, c)){
            res = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    return res;
}
void insert(int i, int c){
    while(!st[c].empty() && w(i, st[c].back().r, c) >= w(st[c].back().pos, st[c].back().r, c))
        st[c].pop_back();
    if(st[c].empty())
        st[c].push_back(Node{i, cnt[c], i});
    else if(w(i, st[c].back().l, c) <= w(st[c].back().pos, st[c].back().l, c)){
        if(st[c].back().l != i)
            st[c].push_back(Node{i, st[c].back().l - 1, i});
    } else {
        int p = bs(i, c);
        st[c].back().l = p;
        st[c].push_back(Node{i, p - 1, i});
    }
    if(!st[c].empty() && st[c].back().r < i)
        st[c].pop_back();
    else
        st[c].back().l = i;
    dp[mp[c][i]] = w(st[c].back().pos, i, c);
}
signed main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &s[i]);
        rk[i] = ++cnt[s[i]];
        if(cnt[s[i]] == 1)
            mp[s[i]].push_back(0);
        mp[s[i]].push_back(i);
    }
    for(int i = 1; i <= n; i++)
        insert(rk[i], s[i]);
    printf("%lld", dp[n]);
    return 0;
}

分治

这也是一种常见的决策单调性优化 DP 的写法，而且比单调队列还好理解，我们设 DP(int l, int r, int ql, int qr) 表示当前要计算 [l, r] 区间内的 DP 值，且决策点在 [pl, pr] 中。

每次我们暴力算出区间中点处的 DP 值，并记录它的决策点，那么左区间的决策点一定在当前决策点左边，右区间的决策点一定在当前决策点右边，此时就可以分治往下做了。

不过分治并不能解决一切决策单调性问题，它只能解决一层一层 DP 的问题，如果不是一层一层解决问题，很有可能当前分治中心的决策点的 DP 值还没有算出，导致程序出现问题。

P5574 [CmdOI2019] 任务分配问题

这道题目就是典型的区间拆分问题，DP 方程就是经典的 dp_{i, j} = \displaystyle\min_{k = 1}^i dp_{k, j - 1} + w_{k + 1, i}（这里的 w_{i, j} 表示 i 到 j 的顺序对个数）。

我们现在要证明 w 满足交叉优于包含，也就是 w_{j, i} + w_{j + 1, i + 1} \leq w_{j, i + 1} + w_{j + 1, i}。右边相当于 w_{i, j} 加上 w_{i, j}，再加上 [j, i] 中 a 小于 a_{i + 1} 的数字个数，减去 [j, i + 1] 中 a 大于 a_j 的数字个数；左边相当于 w_{i, j} 加上 [j, i] 中 a 小于 a_{i + 1} 的数字个数，再减去 [j, i] 中 a 大于 a_j 的数字个数。我们不知道 a_{i + 1} 与 a_j 那个大，如果 a_{i + 1} < a_j，那么[j, i + 1] 中 a 大于 a_j 的数字个数就等于 [j, i] 中 a 大于 a_j 的数字个数；如果 a_{i + 1} > a_j，那么[j, i + 1] 中 a 大于 a_j 的数字个数就大于 [j, i] 中 a 大于 a_j 的数字个数，因此原式左边一定小于右边，满足四边形不等式，可以优化。

还有一点，这道题区间的贡献不能 O(1) 算，但是我们可以像莫队一样暴力转移，复杂度只会多一个 \log，这是树状数组的复杂度，而莫队不会增加复杂度。可以感性理解一下，看一下下面的代码，我们会发现，除了从上一层转移到下一层时 L, R 会有 O(n) 的变化，其他时候都是左端点往右移一位，这是 O(1) 的，那么每层都只会多出 O(n) 的时间复杂度，因此可以直接莫队。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2.5e4 + 9, K = 29;
int a[N], dp[N][K], n, m;
int t[N];
int lowbit(int x){
    return x & -x;
}
void insert(int i, int x){
    for(; i <= n; i += lowbit(i))
        t[i] += x;
}
int ask(int i){
    int res = 0;
    for(; i > 0; i -= lowbit(i))
        res += t[i];
    return res;
}
int L = 1, R, ans;
int w(int l, int r){
    while(l < L){
        ans += R - L + 1;
        ans -= ask(a[--L]);
        insert(a[L], 1);
    }
    while(R < r){
        ans += ask(a[++R]);
        insert(a[R], 1);
    }
    while(L < l){
        insert(a[L], -1);
        ans += ask(a[L++]);
        ans -= R - L + 1;
    }
    while(r < R){
        insert(a[R], -1);
        ans -= ask(a[R--]);
    }
    return ans;
}
void dac(int l, int r, int ql, int qr, int k){
    if(l > r)
        return;
    int mid = (l + r) >> 1, pos = ql;
    dp[mid][k] = 0x3f3f3f3f;
    for(int i = ql; i <= min(qr, mid); i++)
        if(dp[i - 1][k - 1] + w(i, mid) < dp[mid][k]){
            dp[mid][k] = dp[i - 1][k - 1] + w(i, mid);
            pos = i;
        }
    dac(l, mid - 1, ql, pos, k);
    dac(mid + 1, r, pos, qr, k);
}
int res = 0x3f3f3f3f;
signed main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i++)
        dp[i][0] = 0x3f3f3f3f;
    for(int j = 1; j <= m; j++){
        dac(1, n, 1, n, j);
        res = min(res, dp[n][j]);
    }
    printf("%lld", res);
    return 0;
}

CF868F Yet Another Minimization Problem

这道题目和上一道基本一样，转移方程还是 dp_{i, j} = \displaystyle\min_{k = 1}^i dp_{k, j - 1} + w_{k + 1, i}，不过这里的 w_{i, j} 表示 [i, j] 中相同颜色对数。

我们此处还是要证明 w_{j, i} + w_{j + 1, i + 1} \leq w_{j, i + 1} + w_{j + 1, i}，证法和上一题一样，只是这次区间 [i, j] 往左右移动时加上或减去的是区间中与端点数字相同的数字个数，然后就可以莫队了。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9, K = 21, INF = 1e18;
int a[N], dp[N][K], n, m;
int cnt[N];
int L = 1, R, ans;
int w(int l, int r){
    while(l < L){
        ans += cnt[a[--L]];
        cnt[a[L]]++;
    }
    while(R < r){
        ans += cnt[a[++R]];
        cnt[a[R]]++;
    }
    while(L < l){
        cnt[a[L]]--;
        ans -= cnt[a[L++]];
    }
    while(r < R){
        cnt[a[R]]--;
        ans -= cnt[a[R--]];
    }
    return ans;
}
void dac(int l, int r, int ql, int qr, int k){
    if(l > r)
        return;
    int mid = (l + r) >> 1, pos = ql;
    dp[mid][k] = INF;
    for(int i = ql; i <= min(qr, mid); i++)
        if(dp[i - 1][k - 1] + w(i, mid) < dp[mid][k]){
            dp[mid][k] = dp[i - 1][k - 1] + w(i, mid);
            pos = i;
        }
    dac(l, mid - 1, ql, pos, k);
    dac(mid + 1, r, pos, qr, k);
}
int res = INF;
signed main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i++)
        dp[i][0] = INF;
    for(int j = 1; j <= m; j++){
        dac(1, n, 1, n, j);
        res = min(res, dp[n][j]);
    }
    printf("%lld", res);
    return 0;
}

CF833B The Bakery

这道题基本上算是上一道题目的双倍经验了，证法不再赘述。

完整代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3.5e4 + 9, K = 59;
int a[N], dp[N][K], n, m;
int cnt[N];
int L = 1, R, ans;
int w(int l, int r){
    while(l < L){
        cnt[a[--L]]++;
        if(cnt[a[L]] == 1)
            ans++;
    }
    while(R < r){
        cnt[a[++R]]++;
        if(cnt[a[R]] == 1)
            ans++;
    }
    while(L < l){
        if(cnt[a[L]] == 1)
            ans--;
        cnt[a[L++]]--;
    }
    while(r < R){
        if(cnt[a[R]] == 1)
            ans--;
        cnt[a[R--]]--;
    }
    return ans;
}
void dac(int l, int r, int ql, int qr, int k){
    if(l > r)
        return;
    int mid = (l + r) >> 1, pos = ql;
    for(int i = ql; i <= min(qr, mid); i++)
        if(dp[i - 1][k - 1] + w(i, mid) > dp[mid][k]){
            dp[mid][k] = dp[i - 1][k - 1] + w(i, mid);
            pos = i;
        }
    dac(l, mid - 1, ql, pos, k);
    dac(mid + 1, r, pos, qr, k);
}
int res;
signed main(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for(int j = 1; j <= m; j++){
        dac(1, n, 1, n, j);
        res = max(res, dp[n][j]);
    }
    printf("%lld", res);
    return 0;
}

线段树分治 + 分治

P5244 [USACO19FEB] Mowing Mischief P

总结

二维 DP 可以用四边形不等式优化的条件：

一维 DP 可以用二分队列优化：

一维 DP 可以用二分栈优化：

WQS 二分

应用场合

当上述决策单调性题目的 n 和 m 都增大到 10^5，似乎单调队列也不能用了，但是我们可以继续用 WQS 二分优化。

WQS 二分主要解决从 n 个物品中选 m 次物品，每个物品有权值，求能选出的的物品的最大 / 最小权值和。

这类问题的难点在于只能选 m 次物品，可能无法达到最优，这会让我们的问题变得复杂，我们考虑现将其简化成没有限制的情况。但是这种简化有一个使用条件，如果设 dp_i 表示选了 i 次物品时的最大权值，那么把所有 (i, dp_i) 画在二维平面上，它构成了一个上凸壳。这比较难理解，我们首先来介绍一下 WQS 二分是如何消除 m 的。

拿求最大值来举例子，如果没有 m 的限制，那么我们的 DP 大致还是按照贪心的思路，能选的越多越好。拿背包问题来说，它最后可能选了大于 m 个物品。这个时候，我们可以将每个物品的价值减小（最好变成负数），这时再来 DP，就会倾向于少选一些物品，这时选择的物品数就有可能为 m 了。因此，我们的思路就是二分这个权值变化量 mid，如果选的物品小于 m，那么就增大 mid，否则就减小，最后答案去掉 mid 的影响即可，不过这样说还是很玄乎，我们还是要把几何图形画出来。

假设原先的 DP 函数构成的凸包长这个样子：

那么我们的答案就是 x = m 的 y 坐标（比如 m = 3，我们需要求出 B 点的纵坐标），不过我们现在只知道这是一个上凸壳，我们并不知道每一段的函数值，这个凸壳暂时是求不出来的。

主流博客中都说是拿一条直线去切这个凸壳，但是我觉得这样并不直观，于是我换了一种方法理解。我们将这个凸壳进行旋转，比如旋转到以下的情况：

(G, H, I, J, K, L 分别对应原先的 A, B, C, D, E, F)

此时我们发现整个凸壳的最高点从 C 变成了 B，而且此时的最大值点对应的 x 也发生了变化。假设旋转角的 \theta，根据和差角公式，旋转后 B 与 O 连线与 x 轴夹角的 \tan 值为 \displaystyle\frac{dp_m - m \tan \theta}{m + dp_m \tan \theta}，那么这个角的 \sin 值就是 \displaystyle\frac{dp_m - m \tan \theta}{\sqrt{dp_m^2 + m^2 \tan^2 \theta + m ^ 2 + dp_m^2 tan^2 \theta}} = \frac{dp_m - m \tan \theta}{\sec \theta \sqrt{dp_m^2 + m^2}}，\cos 值则是 \displaystyle\frac{m + dp_m \tan \theta}{\sec \theta \sqrt{dp_m^2 + m^2}}。而 O 到 B 的距离依然是 \sqrt{dp_m^2 + m^2}，那么新的 B 点的坐标就应该是 (\displaystyle\frac{m + dp_m \tan \theta}{\sec \theta}, \frac{dp_m - m \tan \theta}{\sec \theta})。

此时上凸壳的作用就凸显了出来，那就是整个凸包在旋转过程中，最大值不断在减小。因此我们可以二分 \tan \theta，求出最大值，如果此时最大值对应点的横坐标大于 m，那么就有可能是最终答案，将其计入答案并继续增大旋转角，直到 A 变成最大值，此时最大值对应点横坐标小于 m，那么我们又扩大旋转角

凸性判断

其实这东西比赛的时候一般感性理解就可以了，严格证明一般比较困难。但是还是有方法的。下面我们先给出一道例题，分别用不同的方法证明它的凸性。

有 n 个树坑，要种 m 棵树。树不能栽种于相邻的两个坑。给定长度为 n 的序列 \{a_i\}，表示在每个坑种树的收益，收益可正可负。求种完这 m 棵树最大可能的收益和。

简言之，就是在长度为 n 的链上，求解大小为 m 的最大权独立集的问题。

应用

P5633 最小度限制生成树

这就是一道典型的 WQS 二分的题目。

如果没有满足编号为 s 的节点正好连了 k 条边这一限制，那么这就是一道简单的最小生成树的题目，于是我们考虑干掉这个限制。设 dp_i 表示编号为 s 的节点正好连了 i 条边时最小生成树大小，于是我们现在要证明 (i, dp_i) 会形成一个上凸壳。

P6246 [IOI 2000] 邮局 加强版 加强版

P4383 [八省联考 2018] 林克卡特树

AT_arc168_e Subsegments with Large Sums

Slope Trick