{{category 競技プログラミング,競プロ解説}} !!! AtCoder Beginer Contest 054 - D * [AtCoder Beginer Contest 054 - D Mixing Experiment|https://abc054.contest.atcoder.jp/tasks/abc054_d] !! 解説 * [AtCoder Beginner Contest 054 解説|https://atcoder.jp/img/abc054/editorial.pdf] !! 解説の解説 この問題は [[AtCoder Beginner Contest 004]] - D マーブル、のDPの遷移に近い。AtCoderは3次元DPがお好き。 :: dp[i][j][k]の定義 ::: '''dp[i番目まで見た][aの物質の量][bの物質の量]'''と3次元DPテーブルを立てる ::: '''dp[pos][aq][bq]''' を「0からposまでの薬品を使ってタイプAの物質 aq , タイプBの物質 bq を構成したときの最小予算」として動的計画法を行う {{layout roll,title:DPテーブル検討 {{include_html DP_SpreadSheet, "!Mixing_Experiment_abc054"}} }}