菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
248
0

潜水

原创
05/13 14:22
阅读数 80335

f[i][j]: 表示氧气至少为i,氮气至少为j至少需要的重量.

f[j][k] = min(f[j][k], f[max(0, j - a)][max(0, k - b)] + w);

由实际意义出发 : 如果a > jb > k也是需要转移过来的. 如果这里不转移, f[i][j]的意义就变了:即氧气值为i,氮气值为j至少需要的重量.

#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
inline int lowbit(int x) { return x & (-x); }
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PII pair<int, int>
#define VIT vector<int>
#define x first
#define y second
#define inf 0x3f3f3f3f
int f[100][100];
 
int main() {
    //freopen("in.txt", "r", stdin);
    IO;
    int v1, v2, n;
    cin >> v1 >> v2 >> n;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        for (int j = v1; j >= 0; --j)
            for (int k = v2; k >= 0; --k)
                f[j][k] = min(f[j][k], f[max(0, j - a)][max(0, k - b)] + w);
    }
    cout << f[v1][v2] << '\n';
    return 0;
}


发表评论

0/200
248 点赞
0 评论
收藏