Cow Roller Coaster
Time Limit:2000MS Memory Limit:65536K
Total Submit:797 Accepted:236
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.
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
Hint
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.
Source
USACO 2006 December Silver
在DP题中 状态的选择往往是至关重要的 要满足能完整描叙一个状态的信息 不遗漏 不多余
而有时候却发现一个状态的目标元素有两个。比如这个题目中典型的可以看出 费用和收益是一个状态的2个目标元素。而一般而言碰到这种情况 我们都会把其中一个元素放到状态中去 是一个状态的目标值确定下来做DP 其实从本质上来说 是一个枚举性质的DP 即枚举一个目标元素的所有可能值 在某个具体的值下面做DP
所以 聪明的朋友一定想到了 我们要尽可能将范围小的元素放入状态中 对
所以此题的状态设置为dp[i][j] 代表修建房子到i地址时使用费用为j的时候的最大收益值
这题的状态转移是分散的 因此最好是对于每个Component做一次转移 呵呵
讲了这么多理论 其实没什么深奥的 背包模型想大家应该都非常熟悉了 其实背包模型不是上面所说的一种特例么？只是前面所说的方法可以应用与2个甚至多个目标元素的情况
1
#include <string.h>
2#include <stdio.h>
3#include <algorithm>
4using namespace std;
5
6const int MAXINT = 200000000;
7const int N = 1010;
8const int M = 10010;
9int L, n, cost;
10int dp[N][N]; //iµØÖ·, C×Ücost
11struct Node { int st, l, f, c; } p[M];
12
13bool operator<(const Node& a, const Node& b) { return a.st < b.st; }
14
15#define Max(a, b) ((a) > (b) ? (a) : (b))
16
17int main() {
18 scanf("%d %d %d", &L, &n, &cost);
19 int i, j;
20 for(i = 0; i < n; ++i) {
21 scanf("%d %d %d %d", &p[i].st, &p[i].l, &p[i].f, &p[i].c);
22 }
23
24 sort(p, p + n);
25
26 for(i = 0; i <= L; ++i)
27 for(j = 0; j <= cost; ++j)
28 dp[i][j] = -MAXINT;
29 dp[0][0] = 0;
30
31 for(i = 0; i < n; i++) {
32 int& st = p[i].st, &l = p[i].l, &f = p[i].f, &c = p[i].c;
33 for(j = 0; j < cost; ++j) if(dp[st][j] >= 0) {
34 dp[st + l][j + c] = Max( dp[st+l][j+c], dp[st][j] + f );
35 }
36 }
37
38 int max = -MAXINT;
39 for(i = 0; i <= cost; ++i) { //cost
40 if(dp[L][i] > max)
41 max = dp[L][i];
42 }
43
44 if(max == -MAXINT) max = -1;
45
46 printf("%d\n", max);
47
48 return 0;
49}
50