ABC054: D - Mixing Experiment
問題
解説
価格(=予算)の最小化という点から、DPを使う解法が候補に浮かぶ(常に価格を小さくする方向にメモしていけば良い)。
一方、比率についてはこういった最適性を考えるのが難しい。例えば目的の比に近い比になるのが最適などとは言えない。 よって、比率に関しては全探索が必要になる。
これより、
と状態を考えることができる。 最小値の更新は、番目の薬品を「選んだとき」と「選ばなかったとき」の2パターンが存在する。
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); } int const inf = 1<<29; constexpr int max_n = 41; constexpr int max_m = 500; int dp[max_n][max_m][max_m]; int main() { int N, Ma, Mb; cin >> N >> Ma >> Mb; vector<int> a(N), b(N), c(N); rep(i, N) { cin >> a[i] >> b[i] >> c[i]; } rep(i, max_n) rep(j, max_m) rep(k, max_m) { dp[i][j][k] = inf; } dp[0][0][0] = 0; int min_value = inf; rep(i, N) rep(j, max_m) rep(k, max_m) { if (dp[i][j][k] >= inf) continue; minimize(dp[i + 1][j][k], dp[i][j][k]); auto& target = dp[i + 1][j + a[i]][k + b[i]]; minimize(target, dp[i][j][k] + c[i]); if (j + a[i] > 0 && (j + a[i]) * Mb == (k + b[i]) * Ma) { minimize(min_value, target); } } cout << (min_value < inf ? min_value : -1) << "\n"; }