bzoj 1571: [Usaco2009 Open]滑雪课

http://www.lydsy.com/JudgeOnline/problem.php?id=1571

dp[i][j]表示前i个时间,能力为j所能达到得最大滑雪次数

预处理出，需要能力$<=c$的滑坡滑行的最少时间的坡花费的时间

dp转移，三种情况

1 喝coco汁

2 滑雪

3 学习课程

具体看代码

#include<cstdio>

#include<cstring>

#include<algorithm>

const int maxn = ;

int t,s,n;

inline int read() {

    int x=;char c=getchar();

    while(c<''||c>'') c=getchar();

    while(c<=''&&c>='') x=x*+c-'',c=getchar();

    return x;

}

struct node{

    int s,t,val;

}cla[maxn];

struct ppop {

    int c,d;

}po[maxn];

int dp[maxn][];

int b[maxn];

int main() {

    t=read(),s=read(),n=read();int st=;

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

        cla[i].s=read(),cla[i].t=read(),cla[i].val=read();

        st=std::max(st,cla[i].val);

    }

    std::memset(b,0x3f,sizeof b);

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

        po[i].c=read(),po[i].d=read();

        b[po[i].c]=std::min(b[po[i].c],po[i].d);

    }

    for(int i=;i<=st;++i) b[i]=std::min(b[i],b[i-]);

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

        for(int j=;j<=st;++j) {

            dp[i][j]=-;

        }

    }

    dp[][]=;

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

        for(int j=;j<=st;++j) {                //the stution have not be down

            if(dp[i][j]<)continue;

            dp[i+][j]=std::max(dp[i][j],dp[i+][j]);//drink coco;

            if(i+b[j]<=t)//the time of ski

                dp[i+b[j]][j]=std::max(dp[i+b[j]][j],dp[i][j]+);

            for(int k=;k<=s;k++)// study

                if(i>=cla[k].s&&i+cla[k].t<t)

                    dp[i+cla[k].t][cla[k].val]=std::max(dp[i+cla[k].t][cla[k].val],dp[i][j]);

        }

    }

    int ans=;

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

        ans=std::max(ans,dp[t][i]);

    }

    printf("%d\n",ans);

    return ;

}