アルゴ式

• Q7. ボールと 2 つの箱 | アルゴ式
  • DPの添え字を3変数から2変数にできる
• Q. マス目の経路最適化 (1) | アルゴ式
  • 各列から1つ値を選んで数列を作って、隣り合った値の差の絶対値の総和を最小化
• Q. マス目の経路最適化 (2) | アルゴ式
  • 2×N のマス目を連結になるように移動したときの「マスの値の総和」最小化
• Q. できるだけ多く解く | アルゴ式
• Q. 連続ボーナス (3) | アルゴ式
• Q. どの区間も x 以上に | アルゴ式
• Q. 各区間の総和を大きくしたい | アルゴ式
• Q. 白黒に塗り分ける (3) | アルゴ式
  • いい問題

ICPC

• Yokohama Phenomena (ICPC 2023-Yokohama)
  • 問題の絵

その他の問題

• ABC323 E - Playlist
  • ある時刻で音楽が終了する（または開始する）確率をDPにする。
  • アルゴ式の「できるだけ多く解く」と似ている？
• ABC364 E - Maximum Glutton
  • key, value を入れ替える
    • 「dp[i][甘さ][しょっぱさ] = 食べれる数」だとTLEする
    • 「dp[i][食べれる数][甘さ上限] = しょっぱさ最小値」だと間に合う
      • 食べれる数は80通りくらい。しょっぱさは 10^4 通りくらいなので、逆にしてあげると計算量が抑えられる。

DP の解き方

• DP の定義式（漸化式ではない）を書くようにする