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 背包第三種實現方式的刷表順序相反，需正向遍歷 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 那麼大
  - [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#

知識本無界，有了大學，就有了界