abc054d <dp, 背包>

标签：ab second int abc054d ab2 abc054 first

https://atcoder.jp/contests/abc054/tasks/abc054_d

// https://atcoder.jp/contests/abc054/tasks/abc054_d
// 背包
// 这里开始的时候数据规模想错了, 所以用了map, 实际上可以用数组 (40 * 10)^2 * 40
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 2e9;

void solv()
{
    map<PII, int> f[2];
    f[0][{0, 0}] = 0;
    int n, ma, mb;
    cin >> n >> ma >> mb;
    for (int ii = 1; ii <= n; ii ++)
    {
        int a, b, c;
        int i = ii&1;
        cin >> a >> b >> c;
        for (auto const &it: f[i^1])
        {
            PII ab = it.first;
            PII ab2 = {ab.first + a, ab.second + b};
            if (!f[i].count(ab)) f[i][ab] = it.second;
            else f[i][ab] = min(f[i][ab], it.second);
            if (!f[i].count(ab2)) f[i][ab2] = it.second + c;
            else f[i][ab2] = min(f[i][ab2], it.second + c);
        }
        f[i^1].clear();
    }
    int ans = INF;
    for (auto const &it: f[n&1])
    {
        int a = it.first.first, b = it.first.second, c = it.second;
        if (a && b && ma*b==mb*a) ans = min(ans, c);
    }
    cout << (ans==INF ? -1: ans) << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}

标签：ab,second,int,abc054d,ab2,abc054,first
From： https://www.cnblogs.com/o2iginal/p/17495830.html