トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 054

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

AtCoder Beginer Contest 054 - D

  解説

この問題は AtCoder Beginner Contest 004 - D マーブル、のDPの遷移に近そう。ただし、品物が2つあるので変数は3つ i, j, kなどとすれば良いだろうか?

(より具体的な方針)

  • dp[i番目まで見た][aの物質の量][bの物質の量]と3次元DPテーブルを立てる
    • dp[pos][aq][bq] を「0からposまでの薬品を使ってタイプAの物質 aq , タイプBの物質 bq を構成したときの最小予算」として動的計画法を行う

  満点解法の解説

お名前: コメント: