记录编号	8648	评测结果	AAAAAAAAAA
题目名称	[POI 1998] 潜水员的问题	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.224 s
提交时间	2008-12-02 22:10:35	内存使用	0.32 MiB

/* 
 * Problem: POI1998 ple
 * Author: Guo Jiabao
 * Time: 2008.12.01 21:20:34
 * State: Unsolved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=1001;
const int M_O=80;
const int M_N=M_O;
const int INF=0x7FFFFFF;

int F[2][M_O][M_N];
int P[MAXN],Q[MAXN],C[MAXN];
int N,T_O,T_N,Ans;

void init()
{
	int i,j,k;
	freopen("ple.in","r",stdin);
	freopen("ple.out","w",stdout);
	scanf("%d%d%d",&T_O,&T_N,&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d%d",&P[i],&Q[i],&C[i]);
	}
	for (i=0;i<=1;i++)
	{
		for (j=0;j<M_O;j++)
		{
			for (k=0;k<M_N;k++)
			{
				F[i][j][k]=INF;
			}
		}
		F[i][0][0]=0;
	}
}

void dynamic()
{
	int i,j,k,p;
	Ans=INF;
	for (i=p=1;i<=N;i++,p=!p)
	{
		for (j=1;j<M_O;j++)
		{
			for (k=1;k<M_N;k++)
			{
				F[p][j][k]=F[!p][j][k];
				if (j-P[i]<0 && k-Q[i]<0 && C[i] < F[p][j][k])
					F[p][j][k]=C[i];
				if (j-P[i]>=0 && k-Q[i]>=0 && F[!p][j-P[i]][k-Q[i]] + C[i] < F[p][j][k])
					F[p][j][k]=F[!p][j-P[i]][k-Q[i]] + C[i];
				if (i==N && j>=T_O && k>=T_N && F[p][j][k]<Ans)
					Ans=F[p][j][k];
			}
		}
	}
}

int main()
{
	init();
	dynamic();
	printf("%d",Ans);
	return 0;
}