课程内容

三类优化方法

① 状态转移过程的优化

不改变状态定义，使用一些特殊的数据结构或者算法专门优化转移过程
举例：扔鸡蛋 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$ $d p [i] = m i n {d p [j]} + 1 ∣ j < i, s [j + 1, i] i s p a l i n d r o m e$
      - 状态集合： $dp[j]$ ， $j + 1 \to i$ 位置的字符串是回文字符串
      - 决策： $min$
  - 时间复杂度： $O(n^2)$ ，可以对转移阶段进行优化
- 优化版——转移过程
  - 现象：实际上回文字符串会非常少
  - 优化：提前存储每个回文串的位置
    - 即提前处理得到 $mark$ $m a r k$ 二维数组
      - $mark[i]$ 存储的是所有以 $i$ 位置结尾的回文串们的起始坐标[可能不止一个]
    - 因此，在转移过程中，利用处理好的 $mark$ 数组，可以避免掉大量的重复循环遍历判断回文串的过程
  - 状态转移方程 👉 $dp[i]=min\{dp[mark[i][j]-1]\} + 1\ |\ j<i$ $d p [i] = m i n {d p [m a r k [i] [j] - 1]} + 1 ∣ j < i$
    - 状态集合大小： $sizeof(mark[i])$ ，即该子串中的回文串数量
  - 时间复杂度： $O(n \times m)$ ， $m$ 代表字符串中回文串的数量
代码
- 普通版
  - 字符串和dp数组错开了一位
    - for循环的 $i$ 、 $j$ 对应dp数组的索引，判断回文串的 $i$ 、 $j$ 要对应到字符串上，所以各-1
  - 初始化 $dp[i]$ $d p [i]$ ，当前字符一定是一个回文 [不管段数，只管可以转移]
    - 其实就是 $j = i -1$ 的情况
  - 时间复杂度： $O(n^2)$ $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$ $1 \to V$ 变成了 $V\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$ $i$ 、楼层数 $j$ $j$ ，观察 $k$ $k$ 与 $dp[i - 1][k - 1]$ $d p [i - 1] [k - 1]$ 、 $dp[i][j - k]$ $d p [i] [j - k]$ 之间的关系
    - 前者 $dp[i - 1][k - 1]$ 与 $k$ 正相关，后者 $dp[i][j - k]$ 与 $k$ 负相关
    - 而要求min(max())，如图所示，就是两者取max后值找min，所以两者相交的地方，就是最优的k值
    - 👉 最优的转移k值，一定发生在两个函数的交点附近[PS：k的取值是离散的]
  - ② 固定鸡蛋数 $i$ $i$ ，再观察楼层数 $j$ $j$ 与最优的 $k$ $k$ 的关系
    - 当楼层数 $j$ 增大时，绿线不受影响，红线整体上移，最优的 $k$ 值也会上移
    - 准确说， $k$ 至少不会变小，因为k值是离散的，楼层数 $j$ 增大一定范围时， $k$ 才增大，总次数才会有增大 [k对应的曲线是阶梯的]
  - 综合两条结论
    - 假设 $dp[i][j-1]$ $d p [i] [j - 1]$ 对应的最优解为 $k_1$ $k_{1}$ ，则 $dp[i][j]$ $d p [i] [j]$ 对应的最优解 $k_2\geq k_1$ $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}$ 要么加一，要么不变【⭐】
      - $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]$ $d p [i - 1] [k - 1] \geq d p [i] [j - k]$ 的最小值也是可以的（令该值为 $k_2$ $k_{2}$ ，相比 $dp[i-1][k-1]\le dp[i][j-k]$ $d p [i - 1] [k - 1] \leq d p [i] [j - k]$ 的最大值 $k_1$ $k_{1}$ ， $k_2=k_1+1\ or\ k_2=k_1$ $k_{2} = k_{1} + 1 o r k_{2} = k_{1}$ ），因为两者的曲线（阶梯状）是对称的（因为第34行若换成 $dp[i - 1][k] <= dp[i][j - k]$ $d p [i - 1] [k] < = d p [i] [j - k]$ ，在OJ上是同样的效果），所以猜测若 $k_2=k_1+1$ $k_{2} = k_{1} + 1$ ， $dp[i-1][k_2-1]=dp[i-1][k_1-1]+1$ $d p [i - 1] [k_{2} - 1] = d p [i - 1] [k_{1} - 1] + 1$ 的同时， $dp[i][j-k_2]=dp[i][j-k_1]-1$ $d p [i] [j - k_{2}] = d p [i] [j - k_{1}] - 1$ ，所以所求的答案 $max\{dp[i-1][k_2-1],\ dp[i][j-k_2]\} + 1$ $m a x {d p [i - 1] [k_{2} - 1], d p [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]$ $v a l [i]$ 的值 👇
      - $dp[i]=k_{first}\ |\ len[k] \ge val[i]$ ，涉及特殊二分00001111，再更新 $len[k_{first}]=val[i]$ 即可
      - 更简洁，后面代码也是这样实现的
  - 可以二分的前提条件是 $len$ $l e n$ 数组的单调性
    - 证明： $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)$ $O (n \times l o g 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)$ $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$ $d p [i] = m i n {d p [j] + (s_{i} - s_{j})^{2} + M} ∣ j < i$ ，其中 $s_i$ $s_{i}$ 为前缀和 $s_i=\sum_{k=1}^ic_k$ $s_{i} = \sum_{k = 1}^{i} c_{k}$
    - 枚举上一段打印的可能终止位置 $j$ ，找最优
  - 时间复杂度： $O(n^2)$
- 斜率优化 [⭐特别优美一类优化算法]
  - ① 分析状态转移公式 [消耗值公式] 的组成
    - 主要是干掉混合项
  - ② 我们实际上要找的是从哪个状态转移更优秀。假设从 $j$ $j$ 转移要优于从 $k$ $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$ $l$ 、 $k$ $k$ 、 $j$ $j$ 三点
    - 【此处场景】直线 $lk$ 的斜率 > 直线 $kj$ 的斜率 [弓背型]
    - 分析两者斜率与 $2s_i$ 的关系，有三种情况，见图中①、②、③
    - 再由斜率关系(Ⅰ)分析：选择从哪点转移最优秀，见九宫格✔处
    - 可见，能成为最优状态的一定没有 $k$
    - 👉 备选答案中，一定没有弓背型
  - ⑤ 最终这个过程转换为：保证候选状态之间，前者斜率一定小不大后者 [非弓背型]
    - 根据斜率关系(Ⅰ)和斜率递增的特点，所求的最优转移状态靠近头部
      - 首先根据斜率关系(Ⅰ)删除头部相关元素 $x_1$ 、 $x_2$ 【出队】
      - 此时剩下的最左边元素即最优转移状态 $x_3$ 【队首】
      - 当有新的状态加 $x_6$ 入时：根据弓背型原则先剔除掉队尾的非备选状态 $x_4$ 、 $x_5$ ，再加入 $x_6$ 【维护单调性 + 入队】
    - 👉 即维护一个【单调队列】，维护一个区间最小值
  - 时间复杂度： $O(n)$
代码
- 关键在于斜率优化的思想，注意运用斜率关系(Ⅰ)公式和斜率比较 (弓背型判断)
- 转换为单调队列的问题：出队→取值→维护单调性→入队
  - 先后顺序根据题意调整
- [PS]
  - 有了斜率优化的思想，根据公式生搬硬套即可
  - 单纯存字符消耗值的数组没有存在的必要，只需要前缀和信息