ABC054 D - Mixing Experiment - ツバサの備忘録

解法

DPをします。
$dp[i][j][k] = i$ 番目までの薬品で、 $A$ が $j$ グラム、 $B$ が $k$ グラムになるような選び方の最小値
とします。
初期値は、 $dp[i][a_i][b_i]=c_i$ 、それ以外は $dp[i][j][k] = \infty$ です。
あとは、
$dp[i][j][k] = min(dp[i][j][k],dp[i-1][j-a_i][k-b_i]+c_i)$
という遷移をしていけば大丈夫です。
最終的な答えは、
$min(dp[n][M_a×p][M_b×p] )$
となります(ここで、 $p$ は1以上です)。