2 从递推到动态规划（下）

课程内容#

三类优化方法#

① 状态转移过程的优化

不改变状态定义，使用一些特殊的数据结构或者算法专门优化转移过程
举例：扔鸡蛋 V2

② 程序实现的优化

状态定义没变、转移过程也没有变
例如：0/1 背包问题，钱币问题 [滚动数组]

③ 状态定义的优化

大量训练才能培养出来的能力，从源头进行优化
举例：扔鸡蛋 V3

【⭐】状态定义 -> 源头，转移过程 -> 过程，程序实现 -> 结果

随堂练习#

——— 动态规划 ——#

HZOJ-46：切割回文#

样例输入

sehuhzzexe

样例输出

思路
- 字符串长度 50 万，注意超时
- 普通版
  - 状态定义 [类似最长上升子序列]
    - $dp [i]$：取字符串的前 $i$ 位，最少分成多少段回文字符串
    - 段数更好理解，等价于最少切的刀数 + 1
  - 状态转移
    - $dp[i]=min{dp[j]} + 1\ |\ j<i,\ s[j+1,\ i]\ is\ palindrome$
      - 状态集合：$dp [j]$，$j + 1 \to i$ 位置的字符串是回文字符串
      - 决策：$min$
  - 时间复杂度：$O (n^2)$，可以对转移阶段进行优化
- 优化版 —— 转移过程
  - 现象：实际上回文字符串会非常少
  - 优化：提前存储每个回文串的位置
    - 即提前处理得到 $mark$二维数组
      - $mark [i]$ 存储的是所有以 $i$ 位置结尾的回文串们的起始坐标[可能不止一个]
    - 因此，在转移过程中，利用处理好的 $mark$ 数组，可以避免掉大量的重复循环遍历判断回文串的过程
  - 状态转移方程 👉$dp [i]=min {dp [mark [i][j]-1]} + 1\ |\ j<i$
    - 状态集合大小：$sizeof (mark [i])$，即该子串中的回文串数量
  - 时间复杂度：$O (n \times m)$，$m$ 代表字符串中回文串的数量
代码
- 普通版
  - 字符串和 dp 数组错开了一位
    - for 循环的 $i$、$j$ 对应 dp 数组的索引，判断回文串的 $i$、$j$ 要对应到字符串上，所以各 - 1
  - 初始化 $dp [i]$，当前字符一定是一个回文 [不管段数，只管可以转移]
    - 其实就是 $j = i -1$ 的情况
  - 时间复杂度：$O (n^2)$
    - 不能单纯看两个循环加判断回文，似乎是 $O (n^3)$，要从均摊时间复杂度的角度考虑
- 优化版
  - 【注意】
    - $mark$ 数组是二维的，第一维用 vector 结构可以不用确定第二维长度 [根据子串的回文串数量变化]，也方便添加起始坐标
    - 各数组的索引起始点，只有字符串从 0 开始
    - 回文串的扩展思路，由中心向两边，需要考虑奇数和偶数个字符

背包类问题：一类【在有限资源下获得最多回报 / 最少成本获得最多回报】的问题

HZOJ-47：0/1 背包#

样例输入

样例输出

思路
- 物品数量有限，只有选 / 不选两种状态
- 状态定义
  - $dp [i][j]$：前 i 件物品，背包最大承重为 j 的情况下，能够获取的最大价值
- 状态转移
  - $dp [i][j] = max\left {\begin {aligned}&dp [i - 1][j]& 没选第 i 件 \&dp [i - 1][j - v [i]] + w [i]& 选了第 i 件 \end {aligned}\right.$
  - 状态集合：没选第 i 件，选了第 i 件，共 2 种状态
  - 决策：$max$
  - 注意题目中：v 代表重量、w 代表价值
- 时间复杂度：$O (n\times V)$
代码
- V1：状态如何定义，程序就如何实现
  - 注意遍历起点，不要漏状态
  - 该种方式不优美
- V2：滚动数组 👉 空间优化
  - i 维度每次只使用当前行与前一行的值，所以只需要 2 维即可
  - 在 i 维度统一模 2即可
- ⭐V3：将程序中的 dp 数组变成 1 维，v、w 数组变成 0 维，修改更新顺序
  - 理解上述代码，需回答 3 个问题：
    - ① 为什么 dp 数组只需要一维
    - ② 为什么不需要 v、w 数组
    - ③ 为什么 $j$ 逆序
  - 解答：
    - ① 思维还在，状态定义还是二维，只是代码实现上的优化
    - ② $i$ 代表的是物品件数，从之前的代码可以看出，v、w 只需关注第 $i$ 件物品，所以可以读入一件物品，处理一件物品
    - ③ 首先理解第①个问题，状态转移代码要保证等式右边的 $dp [j]、dp [j-v]$ 在【物品件数】维度的索引为 $i - 1$；如果正序，$dp [j-v]$ 对应的索引已经变为 i 了，而 $dp [i-1][j-v]$ 已经丢失
  - ❗ 这里 j 的遍历范围从之前的 $1\to V$ 变成了 $V\to v$
    - 这是因为没遍历到的 $v\to 1$ 部分，其值不需要改变，保持即可 [dp 是一维的]
    - 而之前的代码也只是将 $i-1$ 维的值复制过来 [dp 是二维的，否则为初始的 0]

HZOJ-48：完全背包#

样例输入

样例输出

思路
- 状态定义 [类同 0/1 背包]
  - $dp [i][j]$：前 i 种物品，背包最大承重为 j 的情况下，能够获取的最大价值
- 状态转移
  - $dp [i][j] = max\left {\begin {aligned}&dp [i - 1][j]& 没选第 i 种 \&dp [i][j - v [i]] + w [i]& 选了若干个第 i 种 \end {aligned}\right.$
  - ❗ 注意第二种转移状态，不管选了多少个第 i 种物品，物品种数还是前 i 种，因为每种物品有无数件可用，这是和上题最大的区别，有点像上面的钱币问题
    - 这里腾出一个第 i 种物品的空间即可
- 时间复杂度：$O (N \times V)$
代码
- 与上题 0/1 背包第 3 种实现方式的刷表顺序相反，需正向遍历 j，理解上文 [❗] 处即可理解此处

HZOJ-49：多重背包#

样例输入

样例输出

思路
- 普通版
  - 🆒问题模型转换：把每种物品当成多个独立的一件物品来做，从而转换为 0/1 背包问题
  - 状态定义与状态转移与 0/1 背包一致
  - 状态定义
    - $dp [i][j]$：前 i 件物品，背包最大承重为 j 的情况下，能够获取的最大价值
  - 状态转移
    - $dp [i][j] = max\left {\begin {aligned}&dp [i - 1][j]& 没选第 i 件 \&dp [i - 1][j - v [i]] + w [i]& 选了第 i 件 \end {aligned}\right.$
  - 时间复杂度：$O (n\times V\times s)$，可优化
- 优化版 —— 针对转移过程⭐
  - 使用二进制拆分法，减少遍历相同物品的次数
  - 本质上，对于某一类物品，需要我们决定的是具体选择多少件，才是最优答案
  - 举例：1 种物品有 14 件
    - 普通的单一拆分法 —— 需要 14 轮，依次枚举某个种物品选择 $1 \sim s$ 件的所有情况
    - 二进制拆分法 —— 只需要 4 轮，将 14 件物品分成 1、2、4、7 件物品组成的四堆
      - 可以达到相同的效果，并且拆分出来的数量会更少
      - 每次拆分的数量是上一堆的两倍，不够拆了就放剩下全部的即可
    - 拆分 $s$ 件物品的份数比较：普通拆分法：$s$ 份；二进制拆分法：$log\ s$ 份
  - 时间复杂度：$O (V\times \sum_{i=1}^{n}{logs_i})\approx O (n \times V\times log\ s)$
  - [PS] 只能用二进制拆分
    - 对于每堆物品，只有选与不选两种状态，因为在转移过程中，也只有转与不转两种结果
    - 所以无法用其它进制
- 最优时间复杂度：$O (n \times V)$—— 借助单调队列，后续再讲
代码
- V1：当成 0/1 背包问题来做
  - 时间效率不高
- V2：优化转移过程
  - 利用二进制拆分法
  - 两倍两倍、从小到大地拆，才能遍历全部情况
  - 在转移方程中考虑件数 $k$

HZOJ-50：扔鸡蛋#

样例输入

2 100

样例输出

思路
- 【探索思路】
  - 解读所求：最坏情况下最少测多少次
    - 测试次数，与测试方法有关
    - 最坏情况，表示测试过程中，运气是最差的
    - 👉 最好策略、最坏运气
  - 举例：2 个鸡蛋，楼高为 100
    - 二分方式：肯定超时，鸡蛋数量有限
      - [最坏情况]
      - 第一个鸡蛋测楼高 50，碎了
      - 第二个鸡蛋只能从第一层楼乖乖往上测
      - 最终需要测 50 次 [最坏情况→硬度是 49]
    - 自定义策略：以 10 层为间隔往上测
      - [最坏情况]
      - 10、20、30、...、100，在 100 时鸡蛋碎了
      - 再 91、92、...、99
      - 最终需要测 19 次 [硬度是 99]
    - 假设测试次数是 x 次
      - [最坏情况，敢测试的楼层数如下，保证测试次数是 x]
      - 第一次：$x$
      - 第二次：$x + (x - 1)$
      - 第三次：$x + (x - 1) + (x - 2)$
      - 最后：$x + (x - 1) + (x - 2) + ... ＋ 1$，加到 1 是为了能测的楼层最多，即最优策略
      - 计算等差数列和：$(x + 1) \times x \div 2>=100$ 时的 x 值，等于 14
      - 可知：2 个鸡蛋测 100 层楼，最多最少测 14 次
  - 启发：固定测试次数的情况，发现测试策略
- V1：普通版
  - 状态定义
    - $dp [i][j]$：用 i 个鸡蛋，测 j 层楼，最坏情况下最少测多少次
  - 状态转移
    - $dp [i][j] = min_k (max\left {\begin {aligned}&dp [i - 1][k - 1]+1 & 鸡蛋碎了 \&dp [i][j - k]+1 & 鸡蛋没碎 \end {aligned})\right.$
    - k：从 k 楼扔鸡蛋
    - max：运气最差
    - min：最少测试次数 [枚举所有的 k，取最小值]
    - 决策：体现在两种状态中取最大值，所有楼层对应的结果种取最小值
  - 该方法思维正确，但存在明显的空间和时间限制，详见代码 ——V1
- V2：优化转移过程
  - V1 版本中有 3 层循环，而针对遍历 $k$ 求 min 的过程进行优化，可以转为 2 层循环
  - ① 固定鸡蛋数 $i$、楼层数 $j$，观察 $k$ 与 $dp [i - 1][k - 1]$、$dp [i][j - k]$ 之间的关系
    - 前者 $dp [i - 1][k - 1]$ 与 $k$ 正相关，后者 $dp [i][j - k]$ 与 $k$ 负相关
    - 而要求 min (max ())，如图所示，就是两者取 max 后值找 min，所以两者相交的地方，就是最优的 k 值
    - 👉 最优的转移 k 值，一定发生在两个函数的交点附近[PS：k 的取值是离散的]
  - ② 固定鸡蛋数 $i$，再观察楼层数 $j$ 与最优的 $k$ 的关系
    - 当楼层数 $j$ 增大时，绿线不受影响，红线整体上移，最优的 $k$ 值也会上移
    - 准确说，$k$ 至少不会变小，因为 k 值是离散的，楼层数 $j$ 增大一定范围时，$k$ 才增大，总次数才会有增大 [k 对应的曲线是阶梯的]
  - 综合两条结论
    - 假设 $dp [i][j-1]$ 对应的最优解为 $k_1$，则 $dp [i][j]$ 对应的最优解 $k_2\geq k_1$[一定]
      - 并且 $k_2$ 仍需满足 $dp [i-1][k_2-1]\leq dp [i][j-k_2]$ 条件 [①]
    - 若满足，$k_2$ 一定是满足该条件的最大值，因为 $k$ 最多加一
    - 所以，增加一层楼层，$k_2$ 要么加一，要么不变【⭐】
      - $k_2= \left {\begin {aligned}&k_1+1&dp [i-1][k_1]\le dp [i][j-k_1 - 1]\&k_1 & 其它 \end {aligned}\right.$
      - 如果 $k_2=k_1+1$ 代入条件 [①] 成立，则 $k_2=k_1+1$
  - 本质优化的是求 min 的过程，时间复杂度已经有了质的飞跃，详见代码 ——V2
- V3：优化状态定义
  - 状态重定义
    - 令原状态定义 $dp [i][j] = x$，$x$ 代表最少最多的测试次数
    - 分析：原状态定义所需存储空间与楼层数 $j$ 相关，而 $j$ 的值域非常大，数组存不下；反观，$x$ 的值域小，如 $i = 2$ 时，$x \le \sqrt {2j}$[根号关系]
    - 技巧：当发现某个自变量与因变量之间存在相关性时，两者可对调
    - ⭐重定义：$dp [i][x] = j$，$i$ 个鸡蛋扔 $x$ 次，最多测多少层楼
  - 状态转移
    - $dp[i][x] = dp[i][x - 1] + dp[i - 1][x - 1] + 1$
    - 所能测的最大楼层数 = 上 [没碎] + 下 [碎了] + 1
    - 注意：dp 数组元素代表的含义已经变为楼层数
    - 此时已不是一个动态规划问题了，而是递推问题，没有决策
  - 最后找第一个使 $dp [n][x]≥m$[所给楼层] 对应的方法数 $x$，即答案
  - 🆒最终解决了 V1 版本的空间和时间限制
  - [PS] 如果值域相差不大，转换就没有意义；找不到相关的变量，也没法转换
- 注意：所有转移公式都是针对鸡蛋数至少 2 个的情况，所以记得初始化 1 个鸡蛋的情况
代码
- V1
  - 对于在一个范围内求最值的情况，一般需要初始化一个极端值
  - 空间限制
    - 此程序所使用的存储空间与楼层数量强相关
    - 而楼层数量达到了 $2^{31}$，所以这种状态定义不能满足需求
    - 👉 需要优化状态定义
  - 时间限制
    - 时间复杂度：$O (n \times m^2)$
    - 当 m 过大时，时间消耗很大
  - [PS] dp 数组第一维可以压缩，利用滚动数组，但第二维压缩的突破口不在此
- V2：转移过程优化
  - 【关键】根据拐点结论，判断此时鸡蛋数 $i$、楼层数 $j$ 对应的最优的 $k$ 是否可以 + 1
  - 时间复杂度 ->$O (n \times m)$
  - [个人思考] 这里拐点结论其实如果是满足 $dp [i-1][k-1]\ge dp [i][j-k]$ 的最小值也是可以的（令该值为 $k_2$，相比 $dp [i-1][k-1]\le dp [i][j-k]$ 的最大值 $k_1$，$k_2=k_1+1\ or\ k_2=k_1$），因为两者的曲线（阶梯状）是对称的（因为第 34 行若换成 $dp [i - 1][k] <= dp [i][j - k]$，在 OJ 上是同样的效果），所以猜测若 $k_2=k_1+1$，$dp [i-1][k_2-1]=dp [i-1][k_1-1]+1$ 的同时，$dp [i][j-k_2]=dp [i][j-k_1]-1$，所以所求的答案 $max {dp [i-1][k_2-1],\ dp [i][j-k_2]} + 1$ 不变
    - 事实上确实是对称的，可用数学归纳法证明
- V3：状态定义优化
  - 已转变为递推问题，dp [][]->f [][]
  - f 数组使用 long long 类型，虽然楼层数最高为 $2^{31}$，在 int 范围内；但鸡蛋数最大为 32，对应楼层数超过 int，可能会发生未定义行为
  - f 数组第二维大小设到了 70000，因为鸡蛋数为 2，楼层数为 $2^{31}$ 时，对应的 x 值为 $65536=2^{16}=\sqrt {2^{31}\times 2}$
  - 程序优化：改成滚动数组存储；可根据楼层数估计 f 数组第二维大小，动态开辟数组，因为不需要每次开 70000 那么大
  - [PS] 也可使用递归 + 记忆化实现

HZOJ-44：最长上升子序列#

样例输入

10
3 2 5 7 4 5 7 9 6 8

样例输出

思路
- 普通版
  - 能够挑出来的最长严格上升子序列[不需要连续挑]
  - 状态定义
    - $dp (i)$：代表以索引为i的元素结尾的最长严格上升序列长度
    - 必须以 i 结尾！
  - 状态转移
    - $dp(i) = max{dp(j)} + 1\ |\ j<i,\ val(j) < val(i)$
    - 所有能够转移到 $dp (i)$ 的状态：满足 $j<i,\ val (j)<val (i)$ 条件的 $f (j)$，共 i 个
    - 决策：$max$
  - 最终答案：$max (f (i))$，在所有的 $dp (i)$ 中取最大值
  - 状态转移的时间复杂度：$O (n^2)$
- 优化版—— 转移过程
  - ⭐增加一个 $len$ 数组，$len [i]$ 代表长度为 $i$ 的 [严格上升] 序列中，末尾最小值
  - 状态转移
    - 引入
      - 参照上图的 $len$ 数组，实际上，$i$ 代表长度，$min$ 代表末尾最小值
      - 思考：当有一个新的 $val [i]=5$ 时，其接在 $len$ 数组中哪个值后最佳？
        
        ① 首先需要满足序列末尾值比它小 👉$len [k] \lt val [i]$
        
        ② 然后序列长度越大越好 👉接入的位置 $i$ 越大越好
      - 转换：在 $len$ 数组中找最后一个小于 $val [i]$ 的值的索引 $k_{last}$，再 + 1 即得接入位置；并更新 $len [k_{last} + 1]$ 的值为 $val [i]$，因为更新前 $val [i]\le len [k+1]$ 是一定成立的，否则 $k_{last}$ 就不是最后一个
      - 即：$dp [i]=k_{last}+1\ |\ len [k] \lt val [i]$，涉及特殊二分11110000
    - 实际上等价于找第一个大于等于 $val [i]$ 的值 👇
      - $dp [i]=k_{first}\ |\ len [k] \ge val [i]$，涉及特殊二分 00001111，再更新 $len [k_{first}]=val [i]$ 即可
      - 更简洁，后面代码也是这样实现的
  - 可以二分的前提条件是 $len$ 数组的单调性
    - 证明：$len$ 数组一定是单调的，即证明
    - ① 初始是单调的
      - 初始的时候设置为 0，∞，∞即可
    - ② 假设更新前是单调的，更新后还是单调的
      - 更新操作：$len [k]=val [i]$
      - 更新前：$len [k-1] <= len_原 [k]$
      - 更新后：$len [k-1] < val [i] =len_新 [k]<=len_原 [k]$
    - 所以，单调
  - 时间复杂度：$O (n\times log\ l)$
    - $l$ 代表最长上升子序列的长度，即答案，也是 $len$ 数组的最终有效长度
    - 使用了二分查找优化转移过程
  - 【关键】维护了一个单调数组，该数组与所求强相关，实际是使用二分优化
代码
- 普通版
  - 数据很大，使用 scanf，而不是 cin
  - 注意两个 max 的含义
  - 状态转移的时间效率低
- 优化版 —— 状态转移
  - 注意单调数组的维护，以及特殊二分0000011111
    - 二分查找时，ans + 1 代表每加入一个元素，最大长度最多 + 1
  - ans 代表 len 数组中最后一位非极大值的下标，也是当前序列的最大上升子序列最大长度
  - [PS]
    - 不需要开 dp、val 数组，每次只用到当前状态的值
    - 使用 memset 设置无穷大操作：为何程序员喜欢将 INF 设置为 0x3f3f3f3f—— 知乎

—— 结合单调队列 / 栈 ——#

基于3 单调栈与单调队列的知识点

HZOJ-51：矩形#

样例输入

6 6
0 1 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1
1 1 1 0 1 1
1 1 1 1 0 1
1 0 1 1 1 1

样例输出

思路
- 递推+ 单调栈
- 注意：结果可能过大，输出时对 100007 取余
- 【常识】左上角坐标 + 右下角坐标 👉 唯一的 1 个小矩形
- 问题转换：先针对一行，右下角坐标落在该行某一点上时，求能构成的合法子矩形数量 [该点对应几个合法的左上角坐标，就有几个子矩形]；再累加所有点的数量即可
- 通过观察，将上述子问题再变成两部分子问题
  - 首先找到左侧离 $x$ 点最近的，小于 $x$ 高度 [向上数连续白色格子的数量] 的位置 $i$
  - 则【状态定义】以 $x$ 作为右下角坐标所能构成的合法子矩形数量 $f (x)$ 满足 👇
  - 【递推公式】$f (x) = f (i) + h_x\times (x - i)$
    - 能以 $i$ 点作为右下角的子矩形数量 $f (i)$，对应合法左上角坐标数量，而这些坐标一定也可以作为 $x$ 点的合法左上角坐标
    - 即：左侧部分合法的矩形个数 $f (i)$➕ 右侧部分合法的矩形个数 $h_x\times (x - i)$
  - 因为需要求解 $x$ 的最近小于值 $i$，所以要用到单调栈
- [启发] 在有查找最近大于小于值的需求，应该想到单调栈 [一般是与其他算法结合]
代码
- 需要使用数组的地方：单调栈、矩形高度、递推状态
- 注意：留虚拟木板、初始化递推状态值、初始化栈底
- 常规的单调栈套路：维护单调性→取值→入栈
- [PS] 取两次余：可防止未取余的 $f [j]$ 与 $ans$ 相加超范围，实际上该题不会超；此外，并不能防止 $f [j]$ 超范围 [如果发生]，因为 $f [j]$ 已经计算完了

HZOJ-52：古老的打字机#

样例输入

6 40
3 3 6 5 1 2

样例输出

思路
- 动态规划+ 单调队列
- 状态定义：$dp [i]$ 代表打印前 $i$ 个字符的最小消耗值
- 状态转移
  - 根据题意：$dp [i]=min {dp [j]+(s_i-s_j)^2+M}\ |\ j<i$，其中 $s_i$ 为前缀和 $s_i=\sum_{k=1}^ic_k$
    - 枚举上一段打印的可能终止位置 $j$，找最优
  - 时间复杂度：$O (n^2)$
- 斜率优化 [⭐特别优美一类优化算法]
  - ① 分析状态转移公式 [消耗值公式] 的组成
    - 主要是干掉混合项
  - ② 我们实际上要找的是从哪个状态转移更优秀。假设从 $j$ 转移要优于从 $k$ 转移移，即消耗值更小，则
    - ↓
    - $dp[j] + (s_i - s_j)^2 + M < dp[k] + (s_i - s_k)^2 + M$
    - ↓
    - $dp[j] + s_j^2 - 2s_is_j<dp[k] + s_k^2 - 2s_is_k$
    - ↓
    - $(dp[j]+s_j^2)-(dp[k]+s_k^2)<2s_i(s_j-s_k)$
  - ③ 进一步转换，变成斜率的模样
    - 令 $f (i)=dp [i]+s_i^2$
    - ↓ 【斜率关系 (Ⅰ) 】
      - $g(j,k)=\frac{f(j)-f(k)}{s_j-s_k}<2s_i$
    - 👉 斜率 [将 $s$ 当成横坐标、$f$ 当成纵坐标]
    - 此时转换为：如果斜率关系 (Ⅰ) 成立，则从 $j$ 转移比 $k$ 更优秀
  - ④ 如何进一步利用斜率关系 (Ⅰ) 呢？分析如下图所示，有 $l$、$k$、$j$ 三点
    - 【此处场景】直线 $lk$ 的斜率 > 直线 $kj$ 的斜率 [弓背型]
    - 分析两者斜率与 $2s_i$ 的关系，有三种情况，见图中①、②、③
    - 再由斜率关系 (Ⅰ) 分析：选择从哪点转移最优秀，见九宫格✔处
    - 可见，能成为最优状态的一定没有 $k$
    - 👉 备选答案中，一定没有弓背型
  - ⑤ 最终这个过程转换为：保证候选状态之间，前者斜率一定小不大后者 [非弓背型]
    - 根据斜率关系 (Ⅰ) 和斜率递增的特点，所求的最优转移状态靠近头部
      - 首先根据斜率关系 (Ⅰ) 删除头部相关元素 $x_1$、$x_2$ 【出队】
      - 此时剩下的最左边元素即最优转移状态 $x_3$【队首】
      - 当有新的状态加 $x_6$ 入时：根据弓背型原则先剔除掉队尾的非备选状态 $x_4$、$x_5$，再加入 $x_6$【维护单调性 + 入队】
    - 👉 即维护一个【单调队列】，维护一个区间最小值
  - 时间复杂度：$O (n)$
代码
- 关键在于斜率优化的思想，注意运用斜率关系 (Ⅰ) 公式和斜率比较 (弓背型判断)
- 转换为单调队列的问题：出队→取值→维护单调性→入队
  - 先后顺序根据题意调整
- [PS]
  - 有了斜率优化的思想，根据公式生搬硬套即可
  - 单纯存字符消耗值的数组没有存在的必要，只需要前缀和信息

Tips#

知识本无界，有了大学，就有了界