P2948 [USACO09OPEN]滑雪课Ski Lessons

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

题意:Bessie去滑雪,限时T,滑雪场有S节课ios

   每节课开始于$m_i$,长度为$l_i$,能够将Bessie的能力值变成$a_i$(注意是变成不是增长)git

   有n个滑雪坡,去滑雪须要$c_i$的能力,而且耗时$d_i$ide

   问Bessie最多能滑几回雪spa

 

 

一看这么多变量,很显然就是DP啦(只是不会而已get

变量:时间,课程,坡,能力,次数(额,咋设状态呢。。。。)string

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define int long long
#define olinr return
#define _ 0
#define love_nmr 0
#define DB double
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-f;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void put(int x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>9)
        put(x/10);
    putchar(x%10+'0');
}
int t;
int s;
int n;
int f[10505][105];    //f[i][j]表示到i时刻,能力值为j的最多滑雪次数
int ks[10505][150];     //ks[i][j]表示在i时刻结束,得到j能力的课程的最晚开始时间
int g[10505];         //g[i]表示到i时刻的最多滑雪次数           
int st[105];          //st[i]表示能力值>=i的最短滑雪时间
signed main()
{
    t=read();
    s=read();
    n=read();
    for(int a,b,c,i=1;i<=s;i++)   //预处理ks
    {
       a=read();
       b=read();
       c=read();
       ks[a+b-1][c]=max(ks[a+b-1][c],a);
    }
    memset(st,0x3f,sizeof st);
    for(int a,b,i=1;i<=n;i++)   //预处理st
    {
        a=read();
        b=read();
        for(int j=100;j>=a;j--)
            st[j]=min(st[j],b);
    }
    memset(f,-0x3f,sizeof f);    //初始值
    f[0][1]=g[0]=0;              //初始能力为1
    for(int i=1;i<=t;i++)
        for(int j=1;j<=100;j++)
        {
            f[i][j]=f[i-1][j];         //啥也不干QAQ
            if(ks[i-1][j]) f[i][j]=max(f[i][j],g[ks[i-1][j]]);    //表示在前一分钟刚刚上完课,niubi了
            if(i-st[j]>=0) f[i][j]=max(f[i][j],f[i-st[j]][j]+1);  //去滑雪
            g[i]=max(g[i],f[i][j]);      //每次更新
        }
    put(g[t]);
    olinr ~~(0^_^0)+love_nmr;
}

 

----olinr