AcWing 1020. 潜水员
原题链接
简单
作者:
妙WA草
,
2022-07-04 09:47:18
,
所有人可见
,
阅读 136
题目描述
AcWing 1020. 潜水员
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int f[30][100],n,m,a,b,c,v;
int main()
{
cin >> m >> v;
cin >> n;
memset(f,0x3f,sizeof f);// 初始化为正无穷
f[0][0] = 0;//氧气体积至少为0,氮气体积至少为0所需的最小重量为0
/*
集合:氧气体积至少为j,空气体积至少为k的所有方案的重量集合
属性:Min
状态转移:f[j][k] = min(f[j][k],f[max(0,j - a)][max(0,k - b)] + c);
因为体积也可能至少为负数,所以负数时也要计算,用f[0][0]的值
*/
for(int i = 1; i <= n; i ++)
{
cin >> a >> b >> c;
for(int j = m; j >= 0; j --)
for(int k = v; k >= 0; k --)
f[j][k] = min(f[j][k],f[max(0,j - a)][max(0,k - b)] + c);
}
cout << f[m][v] << endl;
return 0;
}