ABC054 : D - Mixing Experiment
-
問題
２つのタイプの成分が (a_i,b_i) だけ含まれ、値段が c_i の薬品が N 個あるとき、２つのタイプの成分の比を Ma : Mb にするときの値段の最小値を求める問題。
-
解法
「dp(i, j, k) := i 番目の薬品まで見たとき、２つの成分を (j, k) だけ加えた時の、求められている成分比をつくるために必要なコストの最小値」として DP をやった。a_i, b_i, N が小さいので計算量も O(N^3 * a_sum * b_sum) になるが、余裕で間に合う。
-
解答
Submission #2698809 - AtCoder Beginner Contest 054
