题目：1020. 潜水员
题目描述
潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸：一个为氧气，一个为氮气。
让潜水员下潜的深度需要各种数量的氧和氮。
潜水员有一定数量的气缸。
每个气缸都有重量和气体容量。
潜水员为了完成他的工作需要特定数量的氧和氮。
他完成工作所需气缸的总重的最低限度的是多少？
例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
3 36 120 10 25 129 5 50 250 1 45 130 4 20 119如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
输入格式
第一行有2个整数 m，n。它们表示氧，氮各自需要的量。
第二行为整数 k 表示气缸的个数。
此后的 k 行，每行包括ai，bi，ci，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。
输出格式
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
数据范围
1 ≤ m ≤ 21,
1 ≤ n ≤ 79,
1 ≤ k ≤ 1000,
1 ≤ ai≤ 21,
1 ≤ bi≤ 79,
1 ≤ ci≤ 800
时空限制
1s / 64MB
输入样例
5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119输出样例
249思路
特殊点：
- j − v 1 [ i ] j-v1[i]j−v1[i]、k − v 2 [ i ] k-v2[i]k−v2[i]为负数怎么转移？
看成 0 就行。举个例子，j − v 1 [ i ] j-v1[i]j−v1[i]为负数，意思是不需要氧气了，可以看成氧气为 0。 - 初始化
这里是取最小值，因此将不可达的状态初始化为正无穷即可。对于所有的f [ 0 ] [ j ] [ k ] f[0][j][k]f[0][j][k]，表示的是从前 0 个物品中选且氧≥ j ≥j≥j，氮≥ k ≥k≥k的最小重量，这些状态是不可达的，初始化为正无穷。
代码1（三维数组）
#include<bits/stdc++.h>usingnamespacestd;constintN=1000+10,M=21+10,K=79+10,INF=0x3f3f3f3f;intn,V1,V2,v1[N],v2[N],w[N],f[N][M][K];intmain(){cin>>V1>>V2>>n;for(inti=1;i<=n;i++)cin>>v1[i]>>v2[i]>>w[i];memset(f,0x3f,sizeoff);for(inti=0;i<=n;i++)f[i][0][0]=0;for(inti=1;i<=n;i++)for(intj=0;j<=V1;j++)for(intk=0;k<=V2;k++)f[i][j][k]=min(f[i-1][j][k],f[i-1][max(0,j-v1[i])][max(0,k-v2[i])]+w[i]);cout<<f[n][V1][V2];return0;}代码2（二维数组）
#include<iostream>#include<cstring>usingnamespacestd;constintMaxV=21+10,MaxM=79+10;intN,V,M,f[MaxV][MaxM];intmain(){cin>>V>>M>>N;memset(f,0x3f,sizeoff);f[0][0]=0;for(inti=1;i<=N;i++){intv,m,w;cin>>v>>m>>w;for(intj=V;j>=0;j--){for(intk=M;k>=0;k--){f[j][k]=min(f[j][k],f[max(0,j-v)][max(0,k-m)]+w);}}}cout<<f[V][M];return0;}