1571. [Usaco2009 Open]滑雪课Ski

2021年09月15日 阅读数:1
这篇文章主要向大家介绍1571. [Usaco2009 Open]滑雪课Ski,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

传送门php

能够想到 $dp$,设 $f[i][j]$ 表示当前等级为 $i$,时间为 $j$ 的最大滑雪次数ios

显然上课不会上让本身等级下降的课,因此第一维 $i$ 知足无后效性ide

而后直接枚举 $i,j$,对于每一个时间 $j$ ,考虑选择滑雪,由于划不一样的坡获得的价值都是 $1$,因此直接取当前能划的时间最少的坡就好了spa

每一个时间 $j$ 枚举完之后再考虑上课,只要考虑能增长等级的课就行了排序

注意不合法的状态是 $-INF$get

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
typedef long long ll;
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=1e4+7,M=107,INF=1e9+7;
int T,n,m,f[M][N],ans;
struct Class{
    int s,t,a;
}C[M];
struct Hillside{
    int tim,lev;
    inline bool operator < (const Hillside &tmp) const {
        return lev<tmp.lev;
    }
}H[N];
int main()
{
    T=read(),n=read(),m=read(); int a,b,c,mxlev=1;
    for(int i=1;i<=n;i++)
    {
        a=read(),b=read(),c=read();
        C[i]=(Class){a,b,c}; mxlev=max(mxlev,c);
    }
    for(int i=1;i<=m;i++)
        H[i].lev=read(),H[i].tim=read();
    sort(H+1,H+m+1);
    memset(f,~0x3f,sizeof(f));//不合法默认-INF
    f[1][0]=0;
    int L=0,tim=INF;//tim是目前耗时最小的坡须要的时间
    for(int i=1;i<=mxlev;i++)
    {
        while(H[L+1].lev<=i&&L<m) L++,tim=min(tim,H[L].tim);//坡已经按等级排序了
        for(int j=0;j<=T;j++)
        {
            if(j+tim<=T) f[i][j+tim]=max(f[i][j+tim],f[i][j]+1);//滑雪,注意时间不能超过T
            f[i][j+1]=max(f[i][j+1],f[i][j]);/*固然也能够什么都不作*/ ans=max(ans,f[i][j]);//更新ans
        }
        for(int j=1;j<=n;j++)
            if(C[i].a>i&&C[i].s+C[i].t<=T)//只考虑能增长等级的课,时间也要合法
                f[C[i].a][C[i].s+C[i].t]=max(f[C[i].a][C[i].s+C[i].t],f[i][C[i].s]);//上课
    }
    printf("%d\n",ans);
    return 0;
}