潜水员为了潜水要使用特殊的装备。
他有一个带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
输入样例:
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例:
249
/*
二维01背包问题;
状态表示:f[i,j,k]:所有从前i个物品中选,且氧气含量 至少 是j,氮气含量 至少 是k的集合
属性:气缸重量总和的最小值;
状态计算:所有不包含物品i的所有选法:f[i - 1,j,k]
所有包含物品i的所有选法:f[i - 1,j - v1,k - v2]
因为至少所以状态计算可以从负数转移;
初始化: 因求最小值把所有的初始状态记为正无穷;
但前0个物品中选,且氧气含量 至少 是0,氮气含量 至少 是0的气缸重量最小值为0;
*/
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N=100;
ll f[N][N];
int main()
{
ll v1,v2,k;
cin>>v1>>v2>>k;
memset(f,0x3f,sizeof(f));
f[0][0]=0;
while(k--)
{
ll a,b,c;
cin>>a>>b>>c;
for(ll i=N-1;i>=0;i--)
for(ll j=N-1;j>=0;j--)
f[i][j]=min(f[i][j],f[max(0,i-a)][max(0,j-b)]+c);
}
cout<<f[v1][v2]<<endl;
}