アルゴ式
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 の定義式(漸化式ではない)を書くようにする