自动搬运

查看原文

来自洛谷，原作者为

	Twilight_ Dear world, please do not fade

搬运于2025-08-24 21:43:44，当前版本为作者最后更新于2017-09-25 22:24:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

观察题目，发现上一节滑雪课所造成的影响就是在这节课结束，和要上的下节课之间的时间空隙中可以滑多少次雪。

很自然地可以联想到枚举所上的课和上这节课之前所上的课。

代码变量解释：

建立状态：dp[i][j]:表示i时刻，j能力值所能滑雪的最大次数；

sl[i]:表示能力值为i时，滑一次雪所需的最小时间；

les[i].co/.st/en:第i节课的能力值/开始时刻/结束时刻；

状态转移方程：

1.dp[x][y]=max(dp[x][y],dp[x2][y2]+q);这节课x时刻结束，能力值为y，上节课x2时刻结束，y2能力值，q表示在上一节课结束和这一节课开始之间一次滑雪的最小时间；

2.dp[x][y2]=dp[x2][y2]+(x-x2)/sl[y2];这节课x时刻结束（但并没有上这节课），上节课x2时刻结束，y2能力值，q表示在上一节课结束和这一节课结束之间一次滑雪的最小时间；

#include<bits/stdc++.h>
using namespace std;
#define maxs 170
int t,s,n,tem,tem2,tem1,ans,sl[10050],dp[20000][maxs];
struct xxx
{
    int st,en,co;
}les[maxs];
bool cmp(xxx a,xxx b)
{
    return a.en<b.en;
}
int main()
{
    cin>>t>>s>>n;
    for(int i=1;i<=s;i++)
    {
        scanf("%d%d%d",&les[i].st,&tem,&les[i].co);
        les[i].en=tem+les[i].st;
    }
    for(int i=0;i<=t+1;i++)sl[i]=999999;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&tem1,&tem2);
        sl[tem1]=min(sl[tem1],tem2);
    }
    for(int i=1;i<=t;i++)sl[i]=min(sl[i],sl[i-1]);    
    sort(les+1,les+1+s,cmp);
    les[0].co=1;les[0].st=0;les[0].en=0;
    for(int i=0;i<=s;i++)
        for(int j=0;j<i;j++)
        {
            int x=les[i].en,y=les[i].co,x2=les[j].en,y2=les[j].co;
            if(x2<les[i].st)
            {
                int q=sl[y2];
                q=(les[i].st-x2)/q;
                dp[x][y]=max(dp[x][y],dp[x2][y2]+q);
            }
            dp[x][y2]=max(dp[x][y2],dp[x2][y2]+(x-x2)/sl[y2]);
        }
    for(int j=0;j<=s;j++)
    {
        int y2=les[j].co,x2=les[j].en;
        if(dp[x2][y2]+(t-x2)/sl[y2]>dp[t][y2])dp[t][y2]=dp[x2][y2]+(t-x2)/sl[y2];
    }
    for(int i=0;i<=s;i++)if(dp[t][les[i].co]>ans)ans=dp[t][les[i].co]; 
    cout<<ans<<endl;
    return 0;
}