记录编号	96186	评测结果	AAAAAAAAAA
题目名称	[POI 1998] 潜水员的问题	最终得分	100
用户昵称	☪Repentance soul	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2014-04-11 16:36:16	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
	freopen("ple.in","r",stdin);
	freopen("ple.out","w",stdout);
	int k,n,m;
	int a[1001];
	int b[1001];
	int c[1001];
	int f[101][101];
	
	memset(f,0x7f,sizeof(f));
	
	f[0][0]=0;
	
	cin>>m>>n>>k;
	
	for(int i=1;i<=k;++i)
	  cin>>a[i]>>b[i]>>c[i];
	  
	for(int i=1;i<=k;++i)
	  for(int j=m;j>=0;--j)
	    for(int l=n;l>=0;--l)
	    {
	    	int r1=j+a[i];
	    	int r2=l+b[i];
	    	
	    	if(r1>m) r1=m;
	    	if(r2>n) r2=n;
	    	if(f[r1][r2]>f[j][l]+c[i])
	    	  f[r1][r2]=f[j][l]+c[i];
	    	
	    }
	
	cout<<f[m][n];
}