Luogu P2948 [USACO09OPEN]滑雪课Ski Lessons

YorkWu

June 1, 2019

1144 views

No comments

860 words

OI 题目

[题目链接](https://www.luogu.org/problemnew/show/P2948 "题目链接")

* * *

现在这蓝题都不好想啊qwq 设计状态：$f\[i\]\[j\]$表示到一门课程结束时间为$i$，能力值为$j$的最多滑雪次数。 所以先给课程按结束时间排个序。 转移： 1. $dp\[x\]\[y\]=max(dp\[x\]\[y\],dp\[x2\]\[y2\]+q)$，$q$是从上节课的结束时刻到这节课的开始时刻的最多滑雪次数。 2. $dp\[x\]\[y2\]=dp\[x2\]\[y2\]+(x-x2)/minn\[y2\]$，$minn\[i\]$是能力值为i时的最小滑雪时间； 代码：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    
    int t,s,n;
    struct clas{
        int begin,end;
        int v;
    }c[109];
    int a[10009][2],minn[10009];
    int f[10009][109];
    
    bool cmp(clas x,clas y){
        return x.end<y.end;
    }
    
    int main(){
        cin>>t>>s>>n;
        memset(minn,0x3f,sizeof(minn));
        for(int i=1;i<=s;i++){
            cin>>c[i].begin>>c[i].end>>c[i].v;
            c[i].end+=c[i].begin;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i][0]>>a[i][1];
            minn[a[i][0]]=min(minn[a[i][0]],a[i][1]);
        }
        for(int i=1;i<=100;i++) minn[i]=min(minn[i],minn[i-1]);
        sort(c+1,c+s+1,cmp);
        c[0].v=1,c[0].begin=0,c[0].end=0;
        for(int i=0;i<=s;i++){
            for(int j=0;j<i;j++){
                int ti1=c[i].end,v1=c[i].v;
                int ti2=c[j].end,v2=c[j].v;
                if(ti2<c[i].begin) f[ti1][v1]=max(f[ti1][v1],f[ti2][v2]+(c[i].begin-ti2)/minn[v2]);
                f[ti1][v2]=max(f[ti1][v2],f[ti2][v2]+(ti1-ti2)/minn[v2]);
            }
        }
        for(int i=0;i<=s;i++){
            int ti=c[i].end,v=c[i].v;
            f[t][v]=max(f[t][v],f[ti][v]+(t-ti)/minn[v]);
        }
        int ans=0;
        for(int i=0;i<=s;i++) ans=max(ans,f[t][c[i].v]);
        cout<<ans;
        return 0;
    }
```

Last modification：March 14, 2020