预处理 + 动态规划

1、数据及其预处理：

　ls[i][j] 表示第i分钟结束，获得能力j的课程的最晚开始时间
　sk[i] 表示能力为i时可以滑的最短坡的时长

　这个两个数据可在读入数据时预处理：

    scanf("%d%d%d",&T,&S,&N);

    for(int i=1;i<=S;i++) 
    {
        scanf("%d%d%d",&m,&l,&a);  //第i门课开始于时刻m，时常l，学习后能力为a
        ls[m+l][a]=max(ls[l+m][a],m);  //计算 ls[m+l][a] 的值
    }
    for(int i=1;i<=n;i++) 
    {
        scanf("%d%d",&c,&d);   //第i个草坡需要能力c，时间需要d
        for(int j=c;j<=100;j++)  //能大于等于c时都可以滑这个坡
            if(!sk[j]||sk[j]>d)
                sk[j]=d;
    }

2、动态规划

　状态函数：
　　　f[i][j] 表示前i时刻，小H能力值为j时可以滑的最多次数
　　　d[i] 表示前i时刻最多可以滑的坡数

　状态转移方程：
　　　每个时刻有三种选择：休息、上课和滑草，于是得到如下状态转移方程
　　　休息：f[i][j]=f[i-1][j]
　　　滑草：当i>=sk[j]时，f[i][j]=max(f[i][j],f[i-sk[j]][j]+1)
　　　上课：当有i时刻结束的课时，f[i][j]=max(f[i][j],d[ls[i-1][j])

　　　d[i]=max(d[i-1],f[i][j])

　边界：
　　f[i][j]=0;
　　d[i]=0;

　答案：
　　Ans=d[t]

　代码：

   for(int i=1;i<=t;i++)
    {
        for(int j=1;j<=5;j++)
        {
            f[i][j]=max(f[i][j],f[i-1][j]);//喝可可 
            if(sk[j]&&i>=sk[j])//滑雪 
                f[i][j]=max(f[i][j],f[i-sk[j]][j]+1);
            if(ls[i-1][j])//上课 
                f[i][j]=max(f[i][j],d[ls[i][j]]);
            d[i]=max(d[i],f[i][j]);
        }
    }