FreeStyleWiki

AtCoder Beginner Contest 054

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 054 - D

  解説

  解説の解説

この問題は 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 を構成したときの最小予算」として動的計画法を行う

+ DPテーブル検討