acwing1020. 潜水员

题目

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

题解

f[i][j]的含义是至少取得i体积氧气和j题解氮气所需的重量，这里是至少那么i和j可以多取，如取f[3][4]时，只有4,4可取，那么此时可以选择取4体积氧气和4体积氮气，即f[3-4][4-4]。由于不能不能取负数下标，那么这里取0就行。

#include<iostream>
#include<cstring>
using namespace std;
const int K=1010;
int a[K],b[K],c[K],f[25][80];

int main(){
    int n,m,k;
    cin>>m>>n>>k;
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    for(int i=0;i<k;i++){
        int a,b,c;
        cin>>a>>b>>c;
        for(int i=m;i>=0;i--){
            for(int j=n;j>=0;j--){
                f[i][j]=min(f[i][j],f[max(0,i-a)][max(0,j-b)]+c);
            }
        }
    }
    cout<<f[m][n]<<endl;
    return 0;
}