【BZOJ】1571: [Usaco2009 Open]滑雪课Ski

【算法】动态规划

【题解】yy出了O(1w log 1w)的算法。

将雪坡排序预处理出g[i]表示能力值为i的最短时长雪坡。

这样就可以定义work(t,c)表示时长t能力c的最多滑雪数量,work(t,c)=t/g[c]。

然后将课程按结束时间排序。

f[i]=f[j]+work(a[i].begin-a[j].end，g[a[j].c])。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cctype>

using namespace std;

const int maxn=,inf=0x3f3f3f3f;

int f[maxn],T,n,m,g[maxn];

struct cyca{int begin,end,c;}a[maxn];

struct cycb{int c,d;}b[maxn];

int read()

{

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

bool cmpb(cycb a,cycb b)

{return a.c<b.c;}

bool cmpa(cyca a,cyca b)

{return a.end<b.end;}

int main(){

    T=read();n=read();m=read();

    for(int i=;i<=n;i++){

        a[i].begin=read()+;

        a[i].end=read();a[i].end+=a[i].begin-;

        a[i].c=read();

    }

    for(int i=;i<=m;i++){

        b[i].c=read();

        b[i].d=read();

    }

    sort(b+,b+m+,cmpb);

    int num=inf;

    for(int i=;i<=m;i++){

        num=min(num,b[i].d);

        g[b[i].c]=num;

    }

    g[]=-;

    for(int i=;i<=;i++)if(!g[i])g[i]=g[i-];

    sort(a+,a+n+,cmpa);

    a[].c=;

    n++;a[n].begin=a[n].end=T+;//a[n].c=inf;

    for(int i=;i<=n;i++){

        f[i]=;

        for(int j=;j<=i-;j++){

            if(a[j].end>=a[i].begin)break;

            //if(a[j].c>=a[i].c)continue;

            f[i]=max(f[i],f[j]+(~g[a[j].c]?(a[i].begin-a[j].end-)/g[a[j].c]:));

        }

    }

    printf("%d",f[n]);

    return ;

}