問題:
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 }