ABC054: D - Mixing Experiment

問題

D - Mixing Experiment

解説

価格(=予算)の最小化という点から、DPを使う解法が候補に浮かぶ(常に価格を小さくする方向にメモしていけば良い)。

一方、比率についてはこういった最適性を考えるのが難しい。例えば目的の比に近い比になるのが最適などとは言えない。 よって、比率に関しては全探索が必要になる。

これより、

dp_{i,j,k} := i個の薬品見たとき、タイプAの量がjで、タイプBの量がkとなるときの価格の最小値

と状態を考えることができる。 最小値の更新は、i番目の薬品を「選んだとき」と「選ばなかったとき」の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";
}