记录编号	244017	评测结果	AAAAAAAAAA
题目名称	[POI 1998] 潜水员的问题	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.069 s
提交时间	2016-03-31 10:21:26	内存使用	4.94 MiB

#include<bits/stdc++.h>
using namespace std;

int Read()
{
	int a=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')	ch=getchar();
	while(ch>='0'&&ch<='9'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	return a;
}

int f[1100][1100]={0},O[1100]={0},N[1100]={0},W[1100]={0};

int GetMin(int a, int b)
{
	return a<b?a:b;
} 

int main()
{
	freopen("ple.in","r",stdin);
	freopen("ple.out","w",stdout);
	int O2=Read(),N2=Read(),num=Read();
	memset(f,0x7f,sizeof(f));
	//把所有气罐都带上，气体肯定够用,初始化为什么都带
	f[0][0]=0;
	//需要0氧气、0氮气时，什么都不带就可以
	for(int i=1;i<=num;i++){
		O[i]=Read();N[i]=Read();W[i]=Read();
	}
	for(int i=1;i<=num;i++){
		for(int j=O2;j>=0;j--){
			//注意逆序，这样可省一维，也就是01背包嘛
			//务必注意到零为止 
			for(int k=N2;k>=0;k--){
				int a=j+O[i],b=k+N[i];
				if(a>O2)	a=O2;
				if(b>N2)	b=N2;
				//氮气、氧气有多余 ，和正好够用是一样的，不用太多考虑 
				f[a][b]=GetMin(f[j][k]+W[i],f[a][b]);
				//把第i个气罐放到容量为a,b的背包中 
				//这时的重量与需要j氧气，k氮气时的重量比较 
				 
			}
		}
	} 
	printf("%d",f[O2][N2]);
	return 0;
}