DP高速化:Monge性の活用(LARSCH)
AtCoder
有志コン
そのまま覚えたいシンプル設定の中堅以上の典型問題
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
DP
ナップサックDP
DP状態:on/off
DP状態:state
DP高速化:直前との比較のみでよい
区間分割型ナップサックDP
DP高速化
f(i,j)をiとjとに分離する
数列
Monge性
DP高速化:Monge性の活用(LARSCH)
最適化テク:緩和しても良い
最大スコア
区間分割の仕方を走査する問題
区間
操作をstackを用いて高速化する
DP高速化:stackの活用
stack
最適化問題
これは学びの深い DP 問題! 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…