ABC 054 D - Mixing Experiment

• 問題

D - Mixing Experiment

• 解法

どれを買ってどれを買わないかという組み合わせは2^40通りなので全探索は無理。このタイプの問題は01ナップサックに似ている。DPを考える。2つの物質の比を考えないといけないが比を見るには物質AとBをどれだけ購入したか分かれば良い。したがって01ナップサックのごとく次のDPが考えられる。

個目まで薬品を見た時に、物質がグラム、物質がグラムとなるような薬品の買い方のうち最小コストとなるもののコスト。

まず初期化をする。dp全体をINF(より大きければ良い)で初期化する。さらにとする。

更新方法を考える。
個目まで薬品を見た状態で、個目の薬品を見た時、物質がグラム、物質がグラムとなるような薬品の買い方のうち最小コストとなるもののコストは

のとき、

そうでない時、

となる。
3重ループを回した後、のうち最小の値を出力する。

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const int INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n,m_a,m_b;
	cin >> n >> m_a >> m_b;
	vector<int> a(n+1),b(n+1),c(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i] >> c[i];
	}

	int dp[41][401][401] = {0};

	for(int i = 0; i <= 40; i++){
		for(int j = 0; j <=400; j++){
			for(int k = 0; k <= 400; k++){
				dp[i][j][k] = INF;
			}
		}
	}

	dp[0][0][0] = 0;
	for(int i = 1; i <= 40; i++){
		for(int j = 400; j >= 0; j--){
			for(int k = 400; k >= 0; k--){
				if(j-a[i]>=0 && k-b[i]>=0){
					dp[i][j][k] = min(dp[i-1][j-a[i]][k-b[i]]+c[i],dp[i-1][j][k]);
				}else{
					dp[i][j][k] = dp[i-1][j][k];
				}
			}
		}
	}

	int ans = INF;
	for(int j = 1; j <= 400; j++){
			for(int k = 1; k <= 400; k++){
				if(k*m_a == j*m_b && dp[n][j][k] < ans) ans = dp[n][j][k];
			}
		}

	if(ans == INF) cout << -1 << endl;
	else cout << ans << endl;

	return 0;
}