潜水员需要特殊装备,包括氧气和氮气气缸。下潜的深度需要特定氧氮比例。他有多个气缸,每个有重量和容量。

  • 输入格式

    • m和n表示氧气和氮气需求。
    • k表示气缸个数。
    • 每个气缸包含ai,bi,ci,表示氧氮容量和重量。
  • 输出格式

    • 输出最低重量总和,以满足需求。
  • 数据范围

    • m、n范围:1≤m≤21,1≤n≤79
    • k范围:1≤k≤1000
    • ai、bi、ci范围:1≤ai≤21,1≤bi≤79,1≤ci≤800

示例输入:

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

示例输出:

249

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 80, M = 22;

int O, H, n, o, h, w, dp[M][N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    cin >> O >> H >> n;
    while(n--) {
        cin >> o >> h >> w;
        for (int i = O; i >= 0; --i)
            for (int j = H; j >= 0; --j)
                dp[i][j] = min(dp[i][j], dp[i - o > 0 ? i - o : 0][j - h > 0 ? j - h : 0] + w);
    }
    cout << dp[O][H];
    return 0;
} 
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status