记录编号	130	评测结果	AAAAAAAAAA
题目名称	[POI 1998] 潜水员的问题	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.272 s
提交时间	2008-04-25 10:41:06	内存使用	0.46 MiB

#include <stdio.h>

#define inf 1100000000
#define maxn 1010
#define maxt 80
#define maxa 80
#define min(x,y) (x)<(y)?(x):(y)

long t,a,n,ans,max,ta,data_t[maxn],data_a[maxn],w[maxn],f[2][maxt*2][maxa*2];
FILE *f1,*f2;

void run(void)
{
	int st,i,p,q;
	for (i=0;i<2;i++)
		for (p=0;p<maxt*2;p++)
			for (q=0;q<maxa*2;q++)
			{
				if (p!=0 || q!=0)
					f[i][p][q]=inf;
			}
	st=0;
	//max+=80;
	for (i=1;i<=n;i++)
	{
		st=1-st;
		for (p=data_t[i];p<=ta+max;p++)
			for (q=data_a[i];q<=ta+max;q++)
			{
				 f[st][p][q]=min( (f[1-st][p-data_t[i]][q-data_a[i]]+w[i]) , (f[1-st][p][q]) );
			}
	}
	ans=inf;
	for (p=t;p<=ta+max;p++)
		for (q=a;q<=ta+max;q++)
		{
			if (f[st][p][q]<ans)
				ans=f[st][p][q];
		}
}

void ini(void)
{
	int i;
	fscanf(f1,"%ld%ld\n%ld",&t,&a,&n);
	if (t>a)
	{
		ta=t;
	}
	if (t<=a)
	{
		ta=a;
	}
	for (i=1;i<=n;i++)
	{
		fscanf(f1,"%ld%ld%ld",&data_t[i],&data_a[i],&w[i]);	
		if (data_t[i]>max)
			max=data_t[i];
		if (data_a[i]>max)
			max=data_a[i];
	}
}

int main(void)
{
	f1=fopen("ple.in","r");
	f2=fopen("ple.out","w");
	ini();
	run();
	fprintf(f2,"%ld\n",ans);
	fclose(f1);fclose(f2);
	return 0;
}