USACO06DEC Cow Roller Coaster

题目地址

题解

先排序，把整个轨道考虑的顺序弄起来，再做01背包。
注意状态的可行性。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int L,n,B,dp[1005][1005];
struct C{
    int l,r,fun,cost;
    bool operator <(C &a){
        return l<a.l||(l==a.l&&r<a.r);
    }
}comp[10005];
void init(){
    L=read(),n=read(),B=read();
    for(int i=1;i<=n;i++)
        comp[i].l=read(),comp[i].r=read()+comp[i].l,
        comp[i].fun=read(),comp[i].cost=read();
    sort(comp+1,comp+1+n);
}
void solve(){
    int c_,l_,r_,f_;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=B;i++)dp[i][0]=0;
    for(int i=1;i<=n;i++){
        c_=comp[i].cost,l_=comp[i].l,r_=comp[i].r,f_=comp[i].fun;
        for(int j=B;j>=c_;j--)
            if(dp[j-c_][l_]>=0)
                dp[j][r_]=max(dp[j][r_],dp[j-c_][l_]+f_);
    }
    printf("%d\n",dp[B][L]);
}
int main(){
    init();
    solve();
    return 0;
}