Edit

【pythonでABC054を解説】D - Mixing Experiment

問題概要

問題ページ

問題文

イルカは、微量の物質Cを生成したいと考えています。
物質Cを生成するためには、タイプAの物質とタイプBの物質の混合比が \(M_a:M_b\) となる溶液を用意する必要があります。
しかし、イルカは薬品を1つも持っていないため、薬局へ薬品を買いに行くことにしました。
薬局では、\(N\) 種類の薬品を取り扱っており、各薬品 \(i\) の在庫はちょうど1つです。
各薬品 \(i\) は、タイプAの物質 \(a_i\) グラム、タイプBの物質 \(b_i\) グラム含んでおり、価格 \(c_i\) 円で売られています。
イルカは、いくつかの薬品を薬局で買います。買った薬品は全て使わなければなりません。
物質Cを生成するために、必要な最小予算を求めてください。
薬局で売られている薬品の組み合わせで、物質Cを生成できない場合はそれを報告してください。

制約

  • \(1≦N≦40\)
  • \(1≦a_i,b_i≦10\)
  • \(1≦c_i≦100\)
  • \(1≦M_a,M_b≦10\)
  • \(gcd(M_a,M_b)=1\)
  • \(a_i\)、\(b_i\)、\(c_i\)、\(M_a\)、\(M_b\)は整数である。

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, ma, mb = list(map(int, input().rstrip('\n').split()))
    abc = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    l = n * 10 +1
    dp = [[10 ** 5] * (l) for _ in range(l)]
    dp[0][0] = 0
    for a, b, c in abc:
        for i in range(l - 1, a - 1, -1):
            for j in range(l - 1, b - 1, -1):
                dp[i][j] = min(dp[i][j], dp[i-a][j-b] + c)
    mn = 10 ** 5
    for i in range(ma, l, ma):
        if int(i * mb / ma) == i * mb / ma:
            j = int(i * mb / ma)
            if 0 <= j < l:
                mn = min(mn, dp[i][j])
    print(-1 if mn == 10 ** 5 else mn)


if __name__ == '__main__':
    solve()

-Edit
-