問題概要
問題ページ
-
-
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()