一提到动态规划的优化，你第一反应想到的是什么？是斜率优化还是四边形不等式，亦或是各种加速转移的辅助数据结构。动态规划作为运筹学的一个重要部分，其本质是数学的是美的。我们除了这些技巧性的方法，还可以尝试从动态规划本身性质入手进行优化。下面就让我们来一同了解动态规划的常见优化思路。

经典例题

说到动态规划的优化，就不得不提到一篇非常经典的国家集训队论文—《优化，再优化！——从<鹰蛋>一题浅析对动态规划算法的优化》。这篇论文很好的阐述了不迷信斜率优化、四边形不等式、数据结构优化，而更多将关注问题本身，关注方程关注转移，将它研究清楚可能会更加有效。下面我们就来一同看看吧。

题目描述

问题简述

有 $n$ 个硬度一样的蛋，我们想要通过下面的方法测量出这些蛋的硬度。
我们身处一栋高为 $m$ 层的楼房，如果一个蛋在第 $i$ 层楼扔下去没有碎，但是从第 $i + 1$ 层楼扔下去碎了，那么我们就说这个蛋的硬度是 $i$。如果在第 $m$ 层扔下去都没有碎，那么这个蛋的硬度就是 $m$；而如果在第 $1$ 层摔下去就碎了，那么硬度就是 $0$。
现在要用这 $n$个蛋来测试这种蛋的硬度，我们想知道在最坏的情况下，在确定硬度的情况下最少的试验次数。

输入描述:

一行两个整数分别表示 $n,m$。

输出描述:

在确定硬度的情况下最少的试验次数。

输入

4 4

输出

3

备注:

$1 \leq n, m \leq 1000$

初步思路

题目求的是 $n$ 个蛋在 $m$ 层楼上实验最坏情况下在确定硬度的情况下最少试验次数。最简单地，题目问什么我们就设什么。我们设 $f[i][j]$ 表示 $i$ 个蛋在 $j$ 层上实验最坏情况下要确定硬度的最小次数。显然 $f[i][0] = 0$，$f[1][j] = j$ ，$1$个蛋的时候只能从第一层开始一层一层从上往下扔不然可能没确定就碎了。其他情况，考虑第一个蛋在哪一层扔：在 $W$ 层扔有两种结果：如果碎了，那么剩下的 $(i-1)$ 个蛋在 $1 - (w - 1)$ 层实验，最坏情况的最小次数为 $f[i - 1][w - 1]$；如果没碎，接下来用剩下的 $i$ 个蛋在 $w + 1 - j$ 层实验——而显然在 $w + 1$ 到 $j$ 层确定硬度和在 $1$ 到 $j - w$ 层确定硬度用的蛋的数量是一样的。所以 $f[i][j] = min_w(max(f[i - 1][w - 1], f[i][j - w]) + 1)$。这时时间复杂度 $O(n^3)$ 很难通过。

问题本身性质

接下来我们观察问题本身的性质，有一个很显然的优化，如果蛋的个数无限多的话——类似于猜数字对区间二分即可——$\lceil \log_2(n+1) \rceil$ 次即可完成。所以 $m > \lceil \log_2(n+1) \rceil$ 时都可以按照二分查找取操作，不用动态规划直接输出 $\lceil \log_2(n+1) \rceil$ 即可。时间复杂度变成了 $O(n^2 \log_2n)$。我们接下来观察方程本身的性质进行优化。显然蛋的数量不变时，楼层数越多可能出现的最坏情况就越坏，所以 $f[i][j] >= f[i][j - 1]$ 始终成立。也就是说 $f[i]$ 单调。我们回顾方程， $f[i][j] = min_w(max(f[i - 1][w - 1], f[i][j - w]) + 1)$，$f[i - 1][w - 1]$ 当 $w$ 增大时单调递增， $f[i][j - w]$ 当 $w$ 增大时单调递减，所以决策点是 $f[i - 1][w - 1]$ 和 $f[i][j - w]$ 函数值交点左右最近的整数点，这个二分查找即可。所以找最优决策点 $w$ 也变成了 $log$ 级别——总复杂度 $O(n \log_2^2 n)$。

观察转移性质

接下来我们对转移进行优化，由于 $f[i][j] = min_w(max(f[i - 1][w - 1], f[i][j - w]) + 1)$，所以 $f[i][j] \le max(f[i - 1][w - 1], f[i][j - w]) + 1$，所以有 $f[i][j] \le f[i - 1][w - 1] + 1$ 并且 $f[i][j] \le f[i][j - w] + 1$，我们取 $w = 1$ 有 $f[i][j] \le f[i][j - 1] + 1$，我们又有 $f[i][j] \ge f[i][j - 1]$。所以 $f[i][j - 1] \le f[i][j] \le f[i][j - 1] + 1$。所以若某一个决策能让 $f[i][j] = f[i][j - 1]$ 那么 $f[i][j] = f[i][j - 1]$ ，否则 $f[i][j] = f[i][j - 1] + 1$。我们看看怎么判断这样一个决策存在。我们维护一个指针 $p$，使得 $p$ 始终满足： $f[i][p] < f[i][j - 1]$ 且 $f[i][p + 1] = f[i][j - 1]$，即 $p$ 指向的是与 $f[i][j - 1]$ 相等的数的最前一个的前一个。而 $f[i][j] = min_w(max(f[i - 1][w - 1], f[i][j - w]) + 1)$，$j - w$ 取 $p$ 的时候， $w - 1$ 为 $j - p - 1$。此时 $f[i][j] = max(f[i - 1][j - p - 1], f[i][p]) + 1$，当 $f[i][p] \ge f[i - 1][j - p - 1]$ 时， $f[i][j] = f[i][j - 1]$：

否则 $f[i][j] = f[i][j - 1] + 1$。这是因为，我们的交点要出现在 $4$ 的右边，不然的话由于取 $max$ 就会如下图：

所以我们只需要根据 $f[i][p]$ 和 $f[i - 1][j - p - 1]$ 的大小就知道转移后的结果，所以这时是 $O(1)$ 转移，总复杂度 $O(n \log_2 n)$。我们只要求最优答案不需要给方案，那就可以考虑能不能直接求解答案如何转移而不去关心真正的转移点在哪。

状态量和求解量

我们继续优化，我们之前设$f[i][j]$ 表示 $i$ 个蛋在 $j$ 层上实验最坏情况下要确定硬度的最小次数，我们交换状态里面已知量和未知量。我们设 $g[i][j]$ 表示 $j$ 个蛋试 $i$ 次最坏情况下能确定 $E$ 最多的层数，最坏我们只需要找到一个最小的 $x$ 使得 $g[ans][n] \ge m$，那么 $ans$ 就是答案。无论多少个鹰蛋，试一次只能确定一层，即 $g[1][j] = 1$；只用一个单试 $i$ 次就可以在 $i$ 层确定 $E$，$g[i][1] = i$。假如第一次就在某一层扔下蛋——如果碎了，那么在之后的 $i-1$ 次里，我们用 $j-1$ 个蛋在下面的楼层里面确定 $E$，我们会希望下面的层数尽量的多，下面的最大层数是 $g[i - 1][j - 1]$；如果没碎，那么在时候的 $i-1$ 次中，我们用 $j$ 个蛋在上面确定 $E$，能确定的最大层数是 $g[i - 1][j]$。所以 $g[i][j] = g[i - 1][j - 1] + g[i - 1][j] + 1$。这个方程没有新的遍历，看起来就是 $蛋的个数 * 实验最多次数$。而实验的最多次数看起来就是 $log_2 n$，天然看起来就是 $n log_2 n$ 的。但其实没有那么多。
我们来观察这个式子 $g[i][j] = g[i - 1][j - 1] + g[i - 1][j] + 1$，这个有点像 $c[i][j] = c[i - 1][j - 1] + c[i - 1][j]$，这个就是排列组合的递推公式，我们知道 $c[1][1],c[1][j] = 0(j > 1),c[i][1] = 1$，所以我们不仅递推式子大于组合数，起始条件也大于组合数，所以我们的 $g[i][j] > c[i][j]$ 恒成立。而我们想找到最小的 $x$ 使得 $g[ans][n] \ge m$，我们就先看看 $c[ans][n] \ge m$ 的解，即 $\frac{ans * (ans - 1) * \dots * (ans - n)}{n!} \ge m$，而 $ans$ 是满足这个式子的最小的数，所以 $c[ans - 1][n] < m$ 即 $\frac{(ans - 1) * \dots * (ans - n)}{n!} < m$，我们移项有 $(ans - 1) * \dots * (ans - n) < m * n!$。我们发现一个很有意思的事情，我们不等式左边是 $n$ 项。除了当 $n = 1$ 时 $ans - 1 < m$，其他情况，$ans$ 最大不会超过与 $\sqrt{m}$ 同阶。这是因为 $(ans - 1) * \dots * (ans - n) < m * n!$ ，首先我们的蛋数也就是 $n$ 趋向于无穷的时候，$ans$ 是趋向 $log_2m$ 的，然后当 $n = 2$ 时，$(ans - 1)(ans - 2) = 2m$ 是一个二次方程， $ans$ 与 $\sqrt{m}$ 是同阶的。我们可以想象到，随着 $n$ 的增大， $ans$ 与 $m$ 的一个函数是不断下沉趋向 $log_2m$ 的。感性理解一下， 最大不会超过与 $\sqrt{m}$ 同阶，当然除了 $n=1$ 的特殊边界情况。到这我们的时间复杂度就变成了 $O(\sqrt{m})$。
这种方法其实暗含了其实在动态规划中，我们状态 $f[i][j] = x$不是两个状态而是三个状态，我们其实是可以考虑把 $x$ 丢进去把 $i$ 或者 $j$ 丢出来变成 $g[x][j]$ 这样的状态可能会更好。这个在背包问题当中是有应用的！

这道题其实经历了四个步骤：发掘问题本身性质——发现状态的性质（单调性）——发现转移的性质——发掘状态量和求解量其实是相对的。这样一步步优化，最终让整道题的复杂度发生了翻天覆地的变化。

思想应用

K连通块

问题描述：$N$ 个点 $M$ 条边，问最少需要加几条边使得图中存在点数恰好为 $k$ 的连通块，数据保证有解。$N,M \le 10^5$。

最简单的，并查集计算出现有连通块大小，跑 $01$ 背包，物品背包上限 $10^5$，背包体积上限 $10^5$，这样复杂度 $O(NK)$，就会 $TLE$。我们发现其实一般的背包问题，物品体积和背包体积是同阶的，也就是说如果全选一般会比背包大很多。但是这道题有个重要的性质就是，所有物品的体积和上限是 $10^5$。我们假设我们物品这时种类有 $k$ 种，每种的重量为 $val_i$，数量为 $num_i$，所以 $\sum val_i * num_i = n$，我们让 $k$ 尽量大时有 $num_i = 1,val_i = i$，此时有不等式 $1 + 2 + \dots + k \le n$，所以 $\frac{k(k+1)}{2} \le 2*n$，也就是说 $k$ 最大的情况下，我们的 $k$ 都才与 $\sqrt{2n}$ 是同阶的！所以我们就对这 $k$ 种物品跑多重背包就好了，这样复杂度大概是 $450 * 10^5$ 也就是 $O(n\sqrt{n})$ 级别的就可以过了。

[$CF506A$]宝藏猎人

问题描述：一共有 $30001$ 个岛屿，下标从 $0$ 到 $30000$，有些岛屿藏有宝藏（第 $i$ 个岛有 $c_i$ 个宝藏）。你从 $0$ 往下标大的方向跳，第一步跳的距离为 $d$。如果上一步跳的距离为 $l$，这一步可以跳 $l - 1$ 或 $l$ 或 $l + 1$（距离必须大于 $0$）。问最多能拿到多少宝藏。

作为 $A$ 题，肯定是不太难的。我们最简单的设 $f[i][j]$ 表示跳到 $i$，上一步跳 $j$ 的最大收益。那我们我们有转移方程 $f[i + j][j] = max(f[i + j][j],f[i][j] + c[i + j])$，$f[i + j + 1][j + 1] = max(f[i + j + 1][j + 1],f[i][j] + c[i + j + 1])$，$f[i + j - 1][j - 1] = max(f[i + j - 1][j - 1],f[i][j] + c[i + j - 1])$。我们看看这时我们的 $i$ 是 $30000$，假如我们的 $j$ 也开 $30000$ 那肯定炸了。由于最大我们有 $1 + 2 + …… + 250 > 30000$，所以第二位最多在第一次的 $d$ 的基础上上下浮动 $250$，所以第二维就开 $500$ 就够了。这时第二维的值 $x = 250$ 表示和 $d$ 相等，$(x - 250) + d$ 才是当前跳跃的距离。

[$CF512B$]狐狸与跳跃

问题描述：给出 $n(n \le 10^6)$ 个不同的数，每个数的值为 $int$ 范围。取第 $i$ 个数的代价为 $c[i]$，求取出若干数使得其最大公约数为 $1$ 的最小代价。

我们设 $f[i][j]$ 表示前 $i$ 个数 $gcd = j$ 的最小代价。对于第 $i$ 个数，假如 $a[i]$ 不选，则 $f[i][j] = min(f[i][j], f[i - 1][j])$；假如 $a[i]$ 选，则 $f[i][j] = min(f[i][j], min_k(f[i - 1][k] + c[i]))$，其中 $gcd(k, a[i]) = j$。但因为我们的每个数为 $int$ 范围，我们的 $gcd$ 也为 $int$ 范围，直接这样开是开不下的。就算我们写成滚动 $f[gcd(a,b)] = min(f[gcd(a,b)], f[a] + cost(b))$但是我们发现能用来做 $gcd$ 的数其实是不多的，也就是说 $gcd$ 的离散的，所以我们用 $map$ 存。所以我们的代码主体如下：

for(int i = 1; i <= n; i++) {
    map<int, int>::iterator it;
    for(it = dp.begin(); it != dp.end(); it++) {
        int t = gcd(num[i], it -> first);
        if(dp.count(t) != 0) dp[t] = min(dp[t], it -> second + c[i]);
        else dp[t] = it -> second + c[i];
    }
}

选人

题目描述：吉吉国王现在想选出 $m(m \le 100)$ 组人来组成部队，现在他有 $n(n \le 10^5)$ 个人可以选择，每个人都有一个战力值 $a_i$。但是吉吉国王非常笨，因此他只能选择连续的一段区间 $[l,r]$ 中的人来组成一个部队，所以选出的这 $m$ 组人在这 $1$ 到 $n$ 个人中没有重合的部分。吉吉国王希望这 $m$ 组人的战斗力之和最大，你需要告诉吉吉国王最大的战斗力之和是多少。

非常经典的问题，选一个区间的时候也就是 $m=1$ 时，我们用 $f[i]$ 表示前 $i$ 个且必需选 $i$ 的最大子串和，那如果 $f[i - 1] >0$，我们就让 $f[i] = f[i - 1] + a[i]$，不然就让 $f[i] = a[i]$。我们不妨设 $f[i][j]$ 为前 $i$ 个数 $i$ 必选，已经挑选了 $j$ 个区间的最大和，所以显然考虑加入上一段还是新开一段就有 $f[i][j] = a[i] + max(f[i - 1][j], f[k][j - 1])$，其中 $1 \le k \le i - 1$。我们画出表格发现其实我们的转移就是红色和橙色两部分转移来的。

所以我们可以一边算一边维护 $max[i][j]$ 表示 $f[i][j]$ 这个数组第 $j$ 列前 $i$ 行的最大值。每次算出 $f[i][j]$ 后，我们用 $max[i][j] = max(max[i - 1][j],f[i][j])$ 维护更新 $max[i][j]$，这样我们的转移就变成了 $f[i][j] = max(f[i - 1][j], max[i - 1][j - 1])$。我们接着考虑 $max[i][j]$ 有什么含义，其实就是前 $i$ 个数不一定选 $i$，选 $j$ 组的最大值。其实我们观察我们之前设的 $f[i][j]$ 其实是不完备的，由于维护的是第 $i$ 个人必须要，所以在更新时就要枚举转移点，因而我们加上了 $max[i][j]$ 来让我们状态变得完备。

但其实我们可以不求列前缀最大值，我们回归我们状态不完备的本质原因来解决。我们其实可以设 $f[i][j][0]$ 表示第 $i$ 个人不选，选 $j$ 个区间的最大收益；设 $f[i][j][1]$ 表示第 $i$ 个人必选，选 $j$ 个区间的最大收益。所以假如第 $i$ 个人不选，我们有 $f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1])$；假如第 $i$ 个人选，我们可以分情况为三种，一是直接贴着上一段，二是和上一段有间隔的新开一段，三是和上一段贴着但是新开一段，所以转移方程有 $f[i][j][1] = a[i] + max(f[i - 1][j][1], f[i - 1][j - 1][0], f[i - 1][j - 1][1])$。

涂色

题目描述：给定一排长度为 $n(n \le 5 * 10^4)$ 的瓷砖，每块瓷砖都有一个数字 $a_i$。现在需要对这些瓷砖进行涂色，每次涂色都可以选一段之前没有涂过的区间，涂色的代价就是这段区间种不同的数字的个数的平方，比如对于 $(1, 3, 3, 4, 2)$，选择对区间 $[2,5]$ 涂色，因为 $2$ 到 $5$ 有 $2, 3, 4$ 三种数字，那么代价就是 $9$。现在需要求出把所有瓷砖都涂上颜色的最小代价。

贪心的想法每次只涂相同的联通段，就会被 $232323232323$ 这样的数据卡掉。我们可以设 $f[i]$ 表示涂完前 $i$ 块的代价，那么 $f[i] = min(f[j] + cost[j + 1][i])$，首先枚举 $i,j$ 就 $O(n^2)$，然后 $cost[i][j]$ 除非空间会炸的预处理以外很难 $O(1)$ 计算。

我们先考虑能不能来个类 $O(n\sqrt{n})$ 的算法，我们知道我们涂一段长度为 $n$，其中不同的数字个数不会超过 $\sqrt{n}$ 个，要不然就不如一个一个涂了。所以我们对于 $f[i] = min(f[j] + cost[j + 1][i])$，每次从后往前枚举 $j$，直到到了 $\sqrt{n}$ 个不同的数。再加一些优化就能到真 $O(n\sqrt{n})$。当年网络赛，有的同学用了一种奇奇怪怪的方法偷鸡，由于数据大概率是随机造出来的，而由于代价平方的存在，就去猜最后的答案除了一些特殊情况，每一段都不会很长，就有同学不停去尝试 $i$ 和 $j$ 最大差多少来枚举转移点，比如 $j$ 从 $i - 100$ 到 $i-1$ 循环，发现超时了；就改成 $j$ 从 $i - 50$ 到 $i-1$ 循环，然后可能 $WA$ 了，就继续提高尝试……
我们接下来来想想正解。如果当前计算到了第 $i$ 位，那么可以将 $a[i]$ 加进来，而之前如果有和 $a[i]$ 值相等的点就可以删掉了，这是因为往前枚举 $j$ 的时候不用再遍历这个点，因为它不会影响到 $j$ 和 $i$ 之间不同的数的个数。保证对于任意一个 $i$，往前遍历 $j$ 的时候，每种颜色只会走一次，这用链表就能实现，每次删掉前面相等的点相当于把它移动到链表头，一次操作的时间复杂度是 $O(1)$ 的。复杂度 $O(n * color)$。那 $color$ 很多的时候怎么办？如果当前遍历到的颜色大于了 $\sqrt{n}$ ，那么这个循环就可以结束了。所以这样就是严格 $O(n\sqrt{n})$ 的。

($CF1348E$)红果和蓝果

题目描述：设有 $n$ 棵树，每个篮子的容量为 $k$，第 $i$ 棵树上的红果和蓝果的数量分别为 $a_i$ 和 $b_i$。现在有很多个篮子，每个篮子要么装同一种颜色，但允许是不同树上的果子；要么只能装同一个树上，但颜色允许不同的果子。现在告诉你篮子的大小 $k$，问你最多可以装满多少个篮子。 $1 \le n,k \le 500, 0 \le a_i,b_i \le 10^9$。

设状态 $f[i][j][l]$ 表示前 $i$ 棵树，红色剩下了 $j$ 个，蓝色的剩下了 $l$ 个装的篮子数。每棵树首先假如红色和蓝色一起装当中红色出 $x$ 个，蓝色出 $y$ 个，那么 $x + y = nk$ 个先装篮子，红色余下 $a[i] - x$，蓝色余下 $b[i] - y$ 个。所以这时 $f[i][(j + a[i] - x) \% k][(l + b[i] - y) \% k] += f[i - 1][j][k] + \frac{x + y}{k} + \frac{j + a[i] - x}{k} + \frac{l + b[i] - y}{k}$。这时我们的时间复杂度就到了 $O(nk^4)$。我们考虑优化一下，我们有个优化，就是不论怎么装，一定每棵树可以变成装一筐混色的，若干框纯色的。我们发现 $f[i][j][l] * k$ 就是用的总的果子数，而红色用了 $suma[i] - j$，所以蓝色用了 $p = f[i][j][l] * k - (suma[i] - j)$ 个，所以 $l = sumb[i] - p$。所以我们用 $f[i][j]$ 表示前 $i$ 棵树装完后，剩下 $j$ 个红果子，最多能装满的篮子数量。剩余的蓝果子的数量 = $前 i 棵树的果子总数 - k * f[i][j] - j$。我们考虑怎么从 $f[i][j]$ 推出去——我们枚举第 $i + 1$ 棵树的红果子的分配：$s$ 个红的和 $k - s$ 个蓝的装一箱，剩下的 $a[i + 1] - s$ 个红果子和之前剩下的 $j$ 个红果子自己装满 $\frac{a[i + 1] - s + j}{k}$ 个箱子，剩下 $(a[i + 1] - s + j) \% k$ 个； $b[i + 1] - k + s$ 个蓝果子和之前剩下的 $sum[i] - k * f[i][j] - j$ 个蓝果子自己装满 $\frac{b[i + 1] - k + s + sum[i] - k * f[i][j] - j}{k}$ 个箱子，剩下 $(b[i + 1] - k + s + sum[i] - k * f[i][j] - j) \% k$ 个。所以在这里我们有 $f[i + 1][(a[i + 1] - s + j) \% k] = max(f[i][j] + 1 + \frac{a[i + 1] - s + j}{k} + \frac{b[i + 1] - k + s + sum[i] - k * f[i][j] - j}{k})$，时间复杂度 $O(nk^2)$。

我们还有一个更好的一种方法，如果我们把红色的果子数记为 $sa$，蓝色的总数记为 $sb$，那么答案一定在 $\lfloor \frac{sa}{k} \rfloor + \lfloor \frac{sb}{k} \rfloor$ 到 $\lfloor \frac{sa}{k} \rfloor + \lfloor \frac{sb}{k} \rfloor + 1$ 筐。我们主要考虑能否到 $\lfloor \frac{sa}{k} \rfloor + \lfloor \frac{sb}{k} \rfloor + 1$，如果要渠道，起码 $sa \% k + sb \% k \ge k$。但是仅有这个条件是不够的，比如$(1, 5)(5,0)(1,5)(5,0)(1,0)$ 就是不能够的。我们设 $f[i][j]$ 表示考虑前 $i$ 棵树内部组合的时候，树上剩余红色的果实数量 $\%k$ 为 $j$ 可不可能。（第二维只有可能性，所以可以用一个 $bitset$ 维护）。$f[0]$ 这一行只有 $sa \% k$ 为 $1$，其他位置为 $0$。之后枚举每棵树，当第 $i$ 棵树的能进行内部的时候去枚举它用 $s$ 棵红色果实和 $k-s$ 个蓝色果实进行内部合并，此时前 $i$ 棵树上的红色果实减少了 $s$ 个——$bitset$ 循环右移 $s$ 位。$f[n]$ 当中如果 $0$ ~ $sa \% k + sb \% k - k$ 种有一个能取到，那就说明我们可以多组成一个内部组合，此时$\lfloor \frac{sa}{k} \rfloor + \lfloor \frac{sb}{k} \rfloor + 1$ 筐就可以取了。而为什么 $f[n]$ 当中如果 $0$ ~ $sa \% k + sb \% k - k$ 种有一个能取到，那就说明我们可以多组成一个内部组合呢？这是因为假设我们红蓝拼色的那一篮用了 $i$ 个红果， $k - i$ 个蓝果，那为了不影响同色的 $\lfloor \frac{sa}{k} \rfloor + \lfloor \frac{sb}{k} \rfloor$ 筐，必须要有 $ 0\le i \le sa \%k$ 并且 $ 0\le k - i \le sb \%k$，而假设最后红果剩下了 $l = sa \% k - i$ 个，那么由上面两个不等式分别有 $ sa \% k - sa \% k \le l \le sa \% k - 0$ 并且 $0 - k + sa \%k \le l \le sb \% k - k + sa \%k $，由于 $sa \% k - sa \% k = 0 \ge 0 - k + sa \%k = sa \% k - k$ 并且 $sb \%k \le sa \%k + sb \% k - k$。联立整理得 $0 \le l \le sa \%k + sb \% k - k$。故得证。

结语

通过这篇 $BLOG$，相信你聪明的脑袋里已经留下了一点对动态规划优化的想法。在之后的 $BLOG$ 中我也会继续沿着这篇 $BLOG$，从技术角度出发，看看那些不推荐盲目使用的斜率优化、四边形不等式之类的到底怎么玩。最后希望你喜欢这篇 $BLOG$！