P2854 [USACO06DEC]牛的过山车Cow Roller Coaster

时间:2022-03-24 00:08:18

题目描述

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.

奶牛们正打算造一条过山车轨道.她们希望你帮忙,找出最有趣,但又符合预算 的方案. 过山车的轨道由若干钢轨首尾相连,由x=0处一直延伸到X=L(1≤L≤1000)处.现有N(1≤N≤10000)根钢轨,每根钢轨的起点 Xi(0≤Xi≤L- Wi),长度wi(l≤Wi≤L),有趣指数Fi(1≤Fi≤1000000),成本Ci(l≤Ci≤1000)均己知.请确定一 种最优方案,使得选用的钢轨的有趣指数之和最大,同时成本之和不超过B(1≤B≤1000).

输入输出格式

输入格式:

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.

输出格式:

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.

输入输出样例

输入样例#1: 复制
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
输出样例#1: 复制
17

说明

Taking the 3rd, 5th and 6th components gives a connected roller-coaster with fun value 17 and cost 7. Taking the first two components would give a more fun roller-coaster (25) but would be over budget.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 2147483647
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define ri register int
template <class T> inline T min(T a, T b, T c)
{
return min(min(a, b), c);
}
template <class T> inline T max(T a, T b, T c)
{
return max(max(a, b), c);
}
template <class T> inline T min(T a, T b, T c, T d)
{
return min(min(a, b), min(c, d));
}
template <class T> inline T max(T a, T b, T c, T d)
{
return max(max(a, b), max(c, d));
}
#define pi acos(-1)
#define me(x, y) memset(x, y, sizeof(x));
#define For(i, a, b) for (int i = a; i <= b; i++)
#define FFor(i, a, b) for (int i = a; i >= b; i--)
#define mp make_pair
#define pb push_back
const int maxn = ;
// name*******************************
int f[][];
int L,n,B;
struct node
{
int x,w,f,c;
} a[];
int ans=-;
// function******************************
bool cmp(node a,node b)
{
return a.x<b.x;
} //***************************************
int main()
{
cin>>L>>n>>B;
For(i,,n)
{
cin>>a[i].x>>a[i].w>>a[i].f>>a[i].c;
}
me(f,-);
sort(a+,a++n,cmp);
f[][]=;
For(i,,n)
{
int u=a[i].x;
int v=a[i].x+a[i].w;
FFor(j,B,a[i].c)
{
if(f[u][j-a[i].c]!=-)
f[v][j]=max(f[v][j],f[u][j-a[i].c]+a[i].f);
}
}
For(i,,B)
ans=max(ans,f[L][i]);
cout<<ans; return ;
}

P2854 [USACO06DEC]牛的过山车Cow Roller Coaster的更多相关文章

  1. bzoj1649 &sol; P2854 &lbrack;USACO06DEC&rsqb;牛的过山车Cow Roller Coaster

    P2854 [USACO06DEC]牛的过山车Cow Roller Coaster dp 对铁轨按左端点排个序,蓝后就是普通的二维dp了. 设$d[i][j]$为当前位置$i$,成本为$j$的最小花费 ...

  2. 洛谷P2854 &lbrack;USACO06DEC&rsqb;牛的过山车Cow Roller Coaster

    P2854 [USACO06DEC]牛的过山车Cow Roller Coaster 题目描述 The cows are building a roller coaster! They want you ...

  3. 【题解】P2854 &lbrack;USACO06DEC&rsqb;牛的过山车Cow Roller Coaster

    P2854 [USACO06DEC]牛的过山车Cow Roller Coaster 题目描述 The cows are building a roller coaster! They want you ...

  4. &lbrack;luoguP2854&rsqb; &lbrack;USACO06DEC&rsqb;牛的过山车Cow Roller Coaster(DP &plus; sort)

    传送门 先按照起点 sort 一遍. 这样每一个点的只由前面的点决定. f[i][j] 表示终点为 i,花费 j 的最优解 状态转移就是一个01背包. ——代码 #include <cstdio ...

  5. BZOJ 1649&colon; &lbrack;Usaco2006 Dec&rsqb;Cow Roller Coaster&lpar; dp &rpar;

    有点类似背包 , 就是那样子搞... --------------------------------------------------------------------------------- ...

  6. bzoj1649 &lbrack;Usaco2006 Dec&rsqb;Cow Roller Coaster

    Description The cows are building a roller coaster! They want your help to design as fun a roller co ...

  7. 【BZOJ】1649&colon; &lbrack;Usaco2006 Dec&rsqb;Cow Roller Coaster(dp)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1649 又是题解... 设f[i][j]表示费用i长度j得到的最大乐趣 f[i][end[a]]=ma ...

  8. BZOJ——1649&colon; &lbrack;Usaco2006 Dec&rsqb;Cow Roller Coaster

    http://www.lydsy.com/JudgeOnline/problem.php?id=1649 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 7 ...

  9. 【bzoj1649】Cow Roller Coaster

    傻逼dp题. dp[i][j]表示用了i长度已花费成本j所能得到的价值. 然后枚举一下铁轨随便做了. 不行就sort一下. #include<bits/stdc++.h> #define ...

随机推荐

  1. 一道java算法题分析

    最近在面试中遇到这样的一道算法题:       求100!的结果的各位数之和为多少?       如:5!=5*4*3*2*1=120,那么他们的和为1+2+0=3这道题不算难,不过倒是注意的细节也有 ...

  2. BOOtstrap源码分析之 tooltip、popover

    一.tooltip(提示框) 源码文件: Tooltip.jsTooltip.scss 实现原理: 1.获取当前要显示tooltip的元素的定位信息(top.left.bottom.right.wid ...

  3. select框默认样式去除(ie中隐藏默认下拉图标)

    html代码 <select class="info-select"> <option selected="selected">1&lt ...

  4. 转自 void- man 差分约束系统详解

    一直不知道差分约束是什么类型题目,最近在写最短路问题就顺带看了下,原来就是给出一些形如x-y<=b不等式的约束,问你是否满足有解的问题 好神奇的是这类问题竟然可以转换成图论里的最短路径问题,下面 ...

  5. 转载----给JavaScript初学者的24条最佳实践

      给JavaScript初学者的24条最佳实践 1.使用 === 代替 == JavaScript 使用2种不同的等值运算符:===|!== 和 ==|!=,在比较操作中使用前者是最佳实践. “如果 ...

  6. 空间闹钟-v1&period;6更新!

    (假设图片无法显示可查看我的qq空间:http://user.qzone.qq.com/805853418/blog/1398785778) 生活助手系列--空间闹钟================= ...

  7. 【方法】Html5实现文件异步上传

    1 简介 开发文件上传功能从来不是一件愉快的事,异步上传更是如此,使用过iframe和Flash的上传方案,也都感觉十分的别扭.本文简要简绍利用Html5的FormData实现文件的异步上传,还可以实 ...

  8. salesforce 得到下拉列表控制依赖值的方法

    salesforce中得到下拉列表的控制依赖值没有系统提供的方法.在网上找了一些,自己也编辑了一下. public static List<Integer> B64ToBytes (Str ...

  9. leaflet 整合 esri

    此 demo 通过 proj4js 将 leaflet 与 esri 整合起来,同时添加了 ClusteredFeatureLayer 的支持. 下载 <html> <head&gt ...

  10. shell-网上lnmp一键安装讲解

    shell-网上lnmp一键安装讲解 #!/bin/bash PATH=/bin:/sbin:/usr/bin:/usr/sbin:/usr/local/bin:/usr/local/sbin:~/b ...