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