水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

ABC054 : D - Mixing Experiment

  • 問題

D - Mixing Experiment

2つのタイプの成分が (a_i,b_i) だけ含まれ、値段が c_i の薬品が N 個あるとき、2つのタイプの成分の比を Ma : Mb にするときの値段の最小値を求める問題。

 

  • 解法

dp(i, j, k) := i 番目の薬品まで見たとき、2つの成分を (j, k) だけ加えた時の、求められている成分比をつくるために必要なコストの最小値」として DP をやった。a_i, b_i, N が小さいので計算量も O(N^3 * a_sum * b_sum) になるが、余裕で間に合う。

 

  • 解答

Submission #2698809 - AtCoder Beginner Contest 054

f:id:babcs2035:20180618214145p:plain