返回题解分享
讨论 / 题解分享/ 帖子详情

拓拓的套餐 - 题解

#include <bits/stdc++.h>
using namespace std;
const int N = 301;
const int INF = 0x3f3f3f3f;
pair<int, int> a[N];
int f[N][N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, x, y, sum1 = 0, sum2 = 0;
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
        sum1 += a[i].first;
        sum2 += a[i].second;
    }
    if (sum1 < x || sum2 < y) {
        cout << "-1\n";
        return 0;
    }
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = x; j >= 0; j--) {
            for (int k = y; k >= 0; k--) {
                int nj = max(0, j - a[i].first);
                int nk = max(0, k - a[i].second);
                f[j][k] = min(f[j][k], f[nj][nk] + 1);
            }
        }
    }
    cout << f[x][y] << "\n";
    return 0;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!