[USACO 2006 Dec S]Cow Roller Coaster

The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget.
The roller coaster will be built on a long linear stretch of land of length L (1 ≤ L ≤ 1,000). The roller coaster comprises a collection of some of the N (1 ≤ N ≤ 10,000) different interchangable components. Each component i has a fixed length Wi (1 ≤ Wi ≤ L). Due to varying terrain, each component i can be only built starting at location Xi (0 ≤ Xi ≤ L - Wi). The cows want to string together various roller coaster components starting at 0 and ending at L so that the end of each component (except the last) is the start of the next component.
Each component i has a "fun rating" Fi (1 ≤ Fi ≤ 1,000,000) and a cost Ci (1 ≤ Ci ≤ 1000). The total fun of the roller coster is the sum of the fun from each component used; the total cost is likewise the sum of the costs of each component used. The cows' total budget is B (1 ≤ B ≤ 1000). Help the cows determine the most fun roller coaster that they can build with their budget.

Line 1: A single integer that is the maximum fun value that a roller-coaster can have while staying within the budget and meeting all the other constraints. If it is not possible to build a roller-coaster within budget, output -1.

#include<bits/stdc++.h> using namespace std; struct ljy{ int a,b,c,d; }f[10010]; int dp[1010][1010]; bool operator <(const ljy &x,const ljy &y){ return x.a<y.a; } int main(){ int l,n,m; cin>>l>>n>>m; for(int i=1;i<=n;i++){ int b; cin>>f[i].a>>b>>f[i].c>>f[i].d; f[i].b=f[i].a+b; } sort(f+1,f+n+1); memset(dp,-1,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=n;i++) for(int j=m;j>=f[i].d;j--) if(dp[f[i].a][j-f[i].d]>=0)dp[f[i].b][j]=max(dp[f[i].b][j],dp[f[i].a][j-f[i].d]+f[i].c); int ans=-1; for(int i=1;i<=m;i++) ans=max(ans,dp[l][i]); cout<<ans<<"\n"; return 0; }

详情