记录编号	28255	评测结果	AAAAAAAAAA
题目名称	[POI 1998] 潜水员的问题	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.145 s
提交时间	2011-10-12 17:47:09	内存使用	6.98 MiB

#include <cstdio>
using namespace std;

int f[1001][22][80];

int fm(int a,int b)//Find Minnum
{
	if (a<b)
		return(a);
	else
		return(b);
}

int mtz(int a)//Minus To Zero
{
	if (a<0)
		return(0);
	else
		return(a);
}

int main(void)
{
	freopen("ple.in","r",stdin);
	freopen("ple.out","w",stdout);
	const int MAXNUM=100000000;
	int i,j,k,temp,O2,N2,n,O2bag[1001],O2sum[1001],N2bag[1001],N2sum[1001],m[1001];
	scanf("%d %d %d %d %d %d",&O2,&N2,&n,&O2bag[1],&N2bag[1],&m[1]);
	O2sum[1]=O2bag[1];
	N2sum[1]=N2bag[1];
	for (i=2;i<=n;i++)
	{
		scanf("%d %d %d",&O2bag[i],&N2bag[i],&m[i]);
		O2sum[i]=O2sum[i-1]+O2bag[i];
		N2sum[i]=N2sum[i-1]+N2bag[i];
	}
	for (i=0;i<=n;i++)
		for (j=0;j<=O2;j++)
			for (k=0;k<=N2;k++)
				f[i][j][k]=MAXNUM;
	f[0][0][0]=0;
	for (i=1;i<=n;i++)
		for (j=0;j<=fm(O2sum[i],O2);j++)
			for (k=0;k<=fm(N2sum[i],N2);k++)
			{
				temp=m[i]+f[i-1][mtz(j-O2bag[i])][mtz(k-N2bag[i])];
				if (temp>f[i-1][j][k])
					temp=f[i-1][j][k];
				f[i][j][k]=temp;
			}
	printf("%d\n",f[n][O2][N2]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}