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

/*
UID:cheepok
PID:ski
LANG:C++
*/
 
#include<stdio.h>
#include<stdlib.h>
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
 
struct orz
{
    int x,y,z;
}a[10001];
 
int k,n,m,ans,v[102],f[102][10001];
 
int cmp(const void *a,const void *b)
{
    return (*(orz *)a).x-(*(orz *)b).x;
}
 
int main()
{
    freopen("ski.in","r",stdin);
    freopen("ski.out","w",stdout);
    int i,j,x,y,z;
    scanf("%d%d%d",&k,&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
        a[i].x+=a[i].y;
    }
    for(i=1;i<=100;i++)
    {
        v[i]=10000000;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        v[x]=min(v[x],y);
    }
    a[++n].x=0;
    a[n].y=0;
    a[n].z=1;
    qsort(a+1,n,sizeof(orz),cmp);
    for(i=2;i<=100;i++)v[i]=min(v[i-1],v[i]);
    for(i=1;i<=n;i++)
    {
        if(a[i].x>k)break;
        for(j=1;j<i;j++)
        f[a[i].z][a[i].x]=max(f[a[i].z][a[i].x],f[a[j].z][a[i].x-a[i].y+1]);
        for(j=a[i].x+1;j<=k;j++)
        {
            if(j>=v[a[i].z])
            f[a[i].z][j]=max(f[a[i].z][j-1],f[a[i].z][j-v[a[i].z]]+1);
            else f[a[i].z][j]=f[a[i].z][j-1];
        }
    }
    for(i=1;i<=n;i++)ans=max(ans,f[a[i].z][k]);
    printf("%d\n",ans);
    return 0;
}