记录编号	293269	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 滑雪训练	最终得分	100
用户昵称	ZXCVBNM_1	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2016-08-10 10:31:37	内存使用	8.83 MiB

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
int M[110],A[110],ks[10010][110],C[10010],D[10010],mn[110],f[10010][110],g[10010];
int read()
{
    int s=0,fh=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
    return s*fh;
}
int main()
{
    freopen("ski.in","r",stdin);
    freopen("ski.out","w",stdout);
    //freopen("in","r",stdin);
    int T,S,N,i,j,L;
    T=read();S=read();N=read();
    memset(ks,0,sizeof(ks));
    for(i=1;i<=S;i++){M[i]=read();L=read();A[i]=read();ks[M[i]+L][A[i]]=max(ks[M[i]+L][A[i]],M[i]);}
    for(i=1;i<=100;i++)mn[i]=INF;
    for(i=1;i<=N;i++)
    {
        C[i]=read();D[i]=read();
        for(j=C[i];j<=100;j++)mn[j]=min(mn[j],D[i]);
    }
    //memset(f,0,sizeof(f));//f[i][j]为到i时,能力为j时的最多滑的次数
    for(i=0;i<=T;i++)
    {
        for(j=1;j<=100;j++)f[i][j]=-INF;
    }
    f[0][1]=0;
    for(i=1;i<=T;i++)
    {
        for(j=1;j<=100;j++)
        {
            if(mn[j]!=INF&&i-mn[j]>=0)f[i][j]=max(f[i][j],f[i-mn[j]][j]+1);
            if(ks[i][j]!=0)f[i][j]=max(f[i][j],g[ks[i][j]]);
            if(i>=1)f[i][j]=max(f[i][j],f[i-1][j]);
            g[i]=max(g[i],f[i][j]);
        }
    }
    printf("%d",g[T]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}