问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1456思路:
这题就是个悲剧...
都说这题是贪心，还有并查集的优化，不过我对于贪心一直不敢用，因为不知道为什么可以贪心
然后，那就动态规划吧，结果，彻底受打击了，对于动态规划还是没掌握啊...
其实，用value[i][j]来表示前i件product到时刻j为止所得到的最大profit
value[i][j] = max (value[i-1][j], value[i-1][j-1]+profit[i])
跟01背包的形式是一样的，所以就可以用滚动数组进行空间优化
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 10001
5 #define Max(a,b) ((a)<(b)?(b):(a))
6 struct Prod {
7 int profit;
8 int deadline;
9 } prods[MAX_N];
10 int n, upper, value[MAX_N];
11
12 int
13 compare(const void *arg1, const void *arg2) /* ascend order: deadline */
14 {
15 struct Prod *a = (struct Prod *)arg1;
16 struct Prod *b = (struct Prod *)arg2;
17 return a->deadline-b->deadline;
18 }
19
20 void
21 init()
22 {
23 int i;
24 for(i=0; i<n; i++)
25 scanf("%d %d", &prods[i].profit, &prods[i].deadline);
26 qsort(prods, n, sizeof(struct Prod), compare);
27 upper = prods[n-1].deadline;
28 }
29
30 void
31 solve()
32 {
33 int i, j;
34 memset(value, 0, sizeof(value));
35 for(i=0; i<n; i++) {
36 for(j=prods[i].deadline; j>=1; j--)
37 value[j] = Max(value[j], value[j-1]+prods[i].profit);
38 for(j=prods[i].deadline+1; j<=upper; j++)
39 value[j] = Max(value[prods[i].deadline], value[j]);
40 }
41 printf("%d\n", value[upper]);
42 }
43
44 int
45 main(int argc, char **argv)
46 {
47 while(scanf("%d", &n) != EOF) {
48 init();
49 solve();
50 }
51 }