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]\ は \ 回文 $
      - 状態集合：$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 配列は 1 つずれている
    - for ループの $i$、$j$ は dp 配列のインデックスに対応し、回文の $i$、$j$ は文字列に対応するため、各 - 1
  - $dp [i]$ を初期化し、現在の文字は必ず回文である [セグメント数に関係なく、遷移できるかどうか]
    - 実際には $j = i -1$ のケース
  - 時間計算量：$O (n^2)$
    - 2 つのループと回文の判断を単純に見ると、$O (n^3)$ のように見えるが、平均時間計算量の観点から考える必要がある
- 最適化版
  - 【注意】
    - $mark$ 配列は二次元で、第一次元は vector 構造を使用し、第二次元の長さを決定する必要はない [部分文字列の回文の数に応じて変化]、また開始座標を追加するのも便利
    - 各配列のインデックスの開始点は、文字列が 0 から始まるのみ
    - 回文の拡張思考は、中心から両側に向かう必要があり、奇数と偶数の文字数を考慮する

ナップサック類問題：限られたリソースで最大のリターンを得る / 最小のコストで最大のリターンを得る問題

HZOJ-47：0/1 ナップサック#

サンプル入力

サンプル出力

思考
- アイテム数は限られており、選択 / 未選択の 2 つの状態のみ
- 状態定義
  - $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 番目のアイテムを選ばなかった場合、選んだ場合の 2 つの状態
  - 決定：$max$
  - 注意：問題中で：v は重量、w は価値を表す
- 時間計算量：$O (n\times V)$
コード
- V1：状態をどのように定義するか、プログラムはそれに従って実装される
  - 遍歴の起点に注意し、状態を漏らさないようにする
  - この方法は美しくない
- V2：ローリングアレイ 👉 空間最適化
  - i 次元は毎回現在の行と前の行の値を使用するだけなので、2 次元で十分
  - i 次元で統一してmod 2を適用する
- ⭐V3：プログラム内の dp 配列を 1 次元にし、v、w 配列を 0 次元にし、更新順序を変更
  - 上記のコードを理解するには、3 つの質問に答える必要がある：
    - ① なぜ dp 配列は 1 次元だけで済むのか
    - ② なぜ v、w 配列は必要ないのか
    - ③ なぜ $j$ は逆順なのか
  - 解答：
    - ① 思考はまだあり、状態定義は依然として二次元であるが、コード実装の最適化に過ぎない
    - ② $i$ はアイテム数を表し、以前のコードからわかるように、v、w は $i$ 番目のアイテムだけを考慮すればよいので、1 つのアイテムを読み込み、処理すればよい
    - ③ まず①の問題を理解し、状態遷移コードは等式の右側の $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 は 1 次元である]
    - 以前のコードも単に $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.$
  - ❗ 注意：2 番目の遷移状態では、いくつの 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 個のアイテムからなる4 つの山に分ける
      - 同じ効果を達成でき、分割された数も少なくなる
      - 各分割の数は前の山の 2 倍で、不足している場合は残りをすべて放置すればよい
    - 分割 $s$ 個のアイテムの数の比較：通常の分割法：$s$ 個；二進法分割法：$log\ s$ 個
  - 時間計算量：$O (V\times \sum_{i=1}^{n}{logs_i})\approx O (n \times V\times log\ s)$
  - [PS] 二進法分割のみ使用可能
    - 各山のアイテムには選択と未選択の 2 つの状態しかないため、遷移プロセスでも選択と未選択の 2 つの結果しかない
    - したがって、他の進数を使用することはできない
- 最適な時間計算量：$O (n \times V)$—— 単調キューを借りて、後で説明する
コード
- V1：0/1 ナップサック問題として解く
  - 時間効率は高くない
- V2：遷移プロセスを最適化
  - 二進法分割法を利用
  - 2 倍、2 倍で、下から上に分割することで、すべての状況を遍歴できる
  - 遷移方程式で件数 $k$ を考慮する

HZOJ-50：卵を投げる#

サンプル入力

2 100

サンプル出力

思考
- 【探索思考】
  - 求めるものを解読する：最悪の状況で最小で何回測定するか
    - 測定回数は、測定方法に関係する
    - 最悪の状況は、測定プロセス中に運が最悪であることを示す
    - 👉 最良の戦略、最悪の運
  - 例：2 つの卵、100 階のビル
    - 二分法：必ずタイムアウト、卵の数は限られている
      - [最悪の状況]
      - 最初の卵で 50 階を測定し、割れた
      - 2 番目の卵は、最初の階から上に測定するしかない
      - 最終的に 50 回測定する必要がある [最悪の状況→硬度は 49]
    - 自定義戦略：10 階ごとに測定する
      - [最悪の状況]
      - 10、20、30、...、100 で、100 で卵が割れた
      - 91、92、...、99 を再度測定
      - 最終的に 19 回測定する必要がある [硬度は 99]
    - 測定回数を $x$ と仮定する
      - [最悪の状況、測定可能な階数は以下の通り、測定回数は $x$ を保証]
      - 最初：$x$
      - 2 回目：$x + (x - 1)$
      - 3 回目：$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 を列挙し、最小値を取る]
    - 決定：2 つの状態の中から最大値を取り、すべての階に対応する結果の中から最小値を取る
  - この方法は思考が正しいが、明らかな空間と時間の制限がある、詳細はコードを参照 ——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 値は、必ず 2 つの関数の交点近くで発生する [PS：k の取値は離散的]
  - ② 卵の数 $i$ を固定し、階数 $j$ と最適な $k$ の関係を観察する
    - 階数 $j$ が増加すると、緑の線は影響を受けず、赤の線は全体的に上に移動し、最適な $k$ 値も上昇する
    - 正確には、$k$ は少なくとも小さくならない、なぜなら k 値は離散的であり、階数 $j$ が増加する一定の範囲で、$k$ も増加し、総測定回数も増加する [k に対応する曲線は階段状である]
  - 総合的な 2 つの結論
    - 仮に $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$ は最大で 1 しか加えられないから
    - したがって、階数を 1 つ増やすと、$k_2$ は 1 つ加えるか、変わらない【⭐】
      - $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]$、特殊な二分探索を含む
    - 実際には最初の大きさを持つ $val [i]$ を見つけることに等しい 👇
      - $dp [i]=k_{first}\ |\ len [k] \ge val [i]$、特殊な二分探索を含む、$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 ではなく
  - 2 つの 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 つの小さな矩形
- 問題の変換：まず 1 行に対して、右下の座標がその行のある点に落ちるとき、構成できる合法的な部分矩形の数を求める [その点に対応するいくつの合法的な左上の座標があるか、つまりいくつの部分矩形があるか]；その後、すべての点の数を累加すればよい
- 観察を通じて、上記の部分問題をさらに 2 つの部分問題に変える
  - まず、左側で $x$ 点に最も近い、小さい $x$ の高さ [上に連続する白いマスの数] の位置 $i$ を見つける
  - したがって【状態定義】$f (x)$ は $x$ を右下の座標として構成できる合法的な部分矩形の数を満たす 👇
  - 【再帰公式】$f (x) = f (i) + h_x\times (x - i)$
    - $i$ 点を右下として構成できる部分矩形の数 $f (i)$ は、合法的な左上の座標の数に対応し、これらの座標は必ず $x$ 点の合法的な左上の座標としても機能する
    - つまり：左側の合法的な矩形の数 $f (i)$➕右側の合法的な矩形の数 $h_x\times (x - i)$
  - $x$ の最近小さい値 $i$ を求める必要があるため、単調スタックを使用する
- [インスピレーション] 最近の大きさや小ささを調べる必要がある場合、単調スタックを考えるべきである [一般的には他のアルゴリズムと組み合わせる]
コード
- 配列を使用する必要がある場所：単調スタック、矩形の高さ、再帰状態
- 注意：仮想の木板を残し、再帰状態の初期値を初期化し、スタックの底を初期化する
- 一般的な単調スタックのルーチン：単調性を維持→値を取る→スタックに入れる
- [PS] 2 回余を取る：未取余の $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$ より優れている
  - ④ どのように傾きの関係 (Ⅰ) をさらに利用するか？以下の図を分析する
    - 【この場面】直線 $lk$ の傾き > 直線 $kj$ の傾き [弓背型]
    - 2 つの傾きと $2s_i$ の関係を分析すると、3 つの状況がある、図中の①、②、③を参照
    - さらに傾きの関係 (Ⅰ) を分析すると、どの点から遷移するのが最も優れているかがわかる、九宮格✔の部分を参照
    - 見ると、最適な状態になるものは必ず $k$ がない
    - 👉 候補の答えの中には必ず弓背型はない
  - ⑤ 最終的にこのプロセスは：候補状態間で、前者の傾きが後者の傾きより小さいことを保証することに変換される
    - 傾きの関係 (Ⅰ) と傾きの増加の特徴に基づいて、求める最適な遷移状態は頭部に近い
      - まず、傾きの関係 (Ⅰ) に基づいて、頭部に関連する要素 $x_1$、$x_2$ を削除する【出隊】
      - この時、残った最左の要素が最適な遷移状態 $x_3$ である【隊首】
      - 新しい状態 $x_6$ を加えるとき：弓背型の原則に基づいて、まず隊尾の非候補状態 $x_4$、$x_5$ を削除し、その後 $x_6$ を追加する【単調性を維持 + 入隊】
    - 👉 つまり、【単調キュー】を維持し、区間の最小値を維持する
  - 時間計算量：$O (n)$
コード
- 傾きの最適化の考え方が重要であり、傾きの関係 (Ⅰ) の公式と傾きの比較（弓背型の判断）に注意する
- 単調キューの問題に変換する：出隊→値を取る→単調性を維持→入隊
  - 順序は問題の意図に応じて調整する
- [PS]
  - 傾きの最適化の考え方があれば、公式を生搬硬套すればよい
  - 単純に文字消費値の配列を保存する必要はなく、前缀和情報だけが必要である

ヒント#

知識には境界がない、大学があれば境界がある