# BZOJ 1649: [Usaco2006 Dec]Cow Roller Coaster (dp，类似01背包)

Posted by 111qqz on Monday, April 11, 2016

## TOC

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 504  Solved: 265 [Submit][Status][Discuss]

## Description

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.

## Input

• Line 1: Three space-separated integers: L, N and B.

• Lines 2..N+1: Line i+1 contains four space-separated integers, respectively: Xi, Wi, Fi, and Ci.

第1行输入L，N，B，接下来N行，每行四个整数Xi，wi，Fi，Ci．

## Output

• 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.

## Sample Input

5 6 10 0 2 20 6 2 3 5 6 0 1 2 1 1 1 1 3 1 2 5 4 3 2 10 2

## Sample Output

17 选用第3条，第5条和第6条钢轨

dp[i][j]表示长度为i，成本为j的最大有趣指数。

bzoj1649题解

/* ***********************************************
Author :111qqz
Created Time :2016年04月11日 星期一 16时43分19秒
File Name :code/bzoj/1649.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E4+3;
int n,l,b;
int dp[1005][1005];
struct node
{
int l,r;
int w;
int f;
int c;

bool operator < (node b) const
{
if (l==b.l) return r<b.r;
return l<b.l;
}

}p[N];
int main()
{
#ifndef  ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif

scanf("%d %d %d",&l,&n,&b);
for ( int i = 1 ; i <= n ; i++)
{
scanf("%d %d %d %d",&p[i].l,&p[i].w,&p[i].f,&p[i].c);
p[i].r = p[i].l + p[i].w;
}

sort(p+1,p+n+1);

ms(dp,-1);
dp[0][0] = 0;
for ( int i = 1 ; i <= n ; i++)
{
for ( int j = p[i].c ;  j <= b ; j++)
if (dp[p[i].l][j-p[i].c]!=-1) dp[p[i].r][j]=max(dp[p[i].r][j],dp[p[i].l][j-p[i].c]+p[i].f);
}
int ans = -1 ; //无解输出-1
for ( int i = 1 ;i <= b ; i++) ans = max(ans,dp[l][i]);
printf("%d\n",ans);

#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}