読者です 読者をやめる 読者になる 読者になる

オンサイトで未確認

ukuku09の活動記録。

AtCoder Beginner Contest 054 D: Mixing Experiment

2月なのでABC埋め。記事は自分用なのであんまりタメにならなそう。

 

問題文

abc054.contest.atcoder.jp

 解法

制約がそんなに大きくないので01ナップザックっぽく解いた。

dp[i][j][k]:=薬品 i-1 まででタイプAが j グラム、タイプBが k グラムの溶液を作る最小金額としてDPする。01ナップザックだから、配列を使いまわすと遷移が

$$dp[j][k] = min(dp[j][k], dp[j-a[i]][k-b[i]] + c[i])$$

みたいに書ける。あとは j:k=Ma:Mb を満たす dp[j][k] のなかの最小金額を求めて終わり。ただし、j=0, k=0 に気をつける(自明。 $O(N^3max(A_i)max(B_i))$ で $1 \leq N \leq 40$、$1 \leq a_i,b_i \leq 10$ なので十分間に合う。

実装は面倒臭かったので $Nmax(A_i)$ と $Nmax(B_i)$ の取りうる最大値(=400)でぶん回した。

 

余談

$N \leq 40$ を見たら半分全列挙というのがあるらしいけど、頭が悪かったのでその発想には至らず。まあ制約が小さかったし多少わね?