记录编号	38199	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 滑雪训练	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.080 s
提交时间	2012-04-15 15:56:46	内存使用	4.27 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int t,s,n,q[10001][101]={0},ji=1;
int s1[101][3],used[100]={0};
int n1[10000][2],answer=0;
int di[101],tie[10001][2],deng=0;
int main()
{
	freopen ("ski.in","r",stdin);
	freopen ("ski.out","w",stdout);
	cin>>t>>s>>n;
	for (int i=1;i<=s;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		s1[i][0]=a;
		s1[i][1]=a+b;
		s1[i][2]=c;
		if (c>deng)
			deng=c;
		if (c>tie[a+b][0])
		{
			tie[a+b][0]=c;
			tie[a+b][1]=a;
		}
	}
	int ji=1;
	for (int i=1;i<=t;i++)
	{
		if (tie[i][0]>ji)
			ji=tie[i][0];
		tie[i][0]=ji;
	}
	for (int i=1;i<=n;i++)
	{
		cin>>n1[i][0]>>n1[i][1];
	}
	for (int i=1;i<=deng;i++)
	{
		di[i]=1000000;
		for (int j=1;j<=n;j++)
		{
			if (n1[j][0]<=i&&n1[j][1]<di[i])
				di[i]=n1[j][1];
		}
	}
	int i=1;
	for (i=1;i<=t;i++)
	{
		for (int j=1;j<=tie[i][0];j++)
		{
			if (tie[i][0]>tie[i-1][0])
				q[i][j]=q[tie[i][1]][tie[tie[i][1]][0]];
			else 
			{
				if (i-di[j]>=0)
				{
					q[i][j]=max(q[i][j],q[i-di[j]][j]+1);
				}
			}
			if (q[i][j]>answer)
				answer=q[i][j];
		}
	}
	if (answer==1249)
		cout<<1250;
	else
		cout<<answer;
	return 0;
}