Submission #1178255

---

Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;

int n, ma, mb, a[40], b[40], c[40], dp[41][401][401];

void init() {
	for (int k = 0; k < 41; k++) {
		for (int i = 0; i < 401; i++) {
			for (int j = 0; j < 401; j++) {
				dp[k][i][j] = 999999;
			}
		}
	}
	dp[0][0][0] = 0;
}

int main() {
	cin >> n >> ma >> mb;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	init();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 401; j++) {
			for (int k = 0; k < 401; k++) {
				if (dp[i][j][k] == 999999) continue;
				dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
				//if(j+a[i] < 401 && k+b[i] < 401)
				dp[i + 1][j + a[i]][k + b[i]] = min(dp[i + 1][j + a[i]][k + b[i]], dp[i][j][k]+c[i]);
			}
		}
	}
	int ans = 999999999;
	for (int i = 1; i < 401; i++) {
		for (int j = 1; j < 401; j++) {
			if (i*ma == j*mb && dp[n][i][j] > 0 && dp[n][i][j] < 999999) {
				//cout << "a:" << i << " b:" << j << " ma:" << ma << " mb:" << mb << endl;
				//cout << "dp[n][i][j]:" << dp[n][i][j] << endl;
				ans = min(ans, dp[n][i][j]);
			}
		}
	}
	if (ans >= 999999)ans = -1;
	cout << ans << endl;
}

Submission Info

Judge Result