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題中 狀態(tài)的選擇往往是至關(guān)重要的 要滿足能完整描敘一個(gè)狀態(tài)的信息 不遺漏 不多余
而有時(shí)候卻發(fā)現(xiàn)一個(gè)狀態(tài)的目標(biāo)元素有兩個(gè)。比如這個(gè)題目中典型的可以看出 費(fèi)用和收益是一個(gè)狀態(tài)的2個(gè)目標(biāo)元素。而一般而言碰到這種情況 我們都會(huì)把其中一個(gè)元素放到狀態(tài)中去 是一個(gè)狀態(tài)的目標(biāo)值確定下來做DP 其實(shí)從本質(zhì)上來說 是一個(gè)枚舉性質(zhì)的DP 即枚舉一個(gè)目標(biāo)元素的所有可能值 在某個(gè)具體的值下面做DP
所以 聰明的朋友一定想到了 我們要盡可能將范圍小的元素放入狀態(tài)中 對(duì)
所以此題的狀態(tài)設(shè)置為dp[i][j] 代表修建房子到i地址時(shí)使用費(fèi)用為j的時(shí)候的最大收益值
這題的狀態(tài)轉(zhuǎn)移是分散的 因此最好是對(duì)于每個(gè)Component做一次轉(zhuǎn)移 呵呵
講了這么多理論 其實(shí)沒什么深?yuàn)W的 背包模型想大家應(yīng)該都非常熟悉了 其實(shí)背包模型不是上面所說的一種特例么？只是前面所說的方法可以應(yīng)用與2個(gè)甚至多個(gè)目標(biāo)元素的情況
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