【HDOJ】2159 FATE

DP+贪心优化。
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 #define MAXNUM 105
 6 
 7 typedef struct {
 8     int exp, deg;
 9 } info_st;
10 
11 info_st infos[MAXNUM];
12 int dp[MAXNUM][MAXNUM];
13 int n, m, k, s;
14 
15 int comp(const void *a, const void *b) {
16     info_st *p = (info_st *)a;
17     info_st *q = (info_st *)b;
18 
19     if (p->deg == q->deg)
20         return q->exp - p->exp;
21     else
22         return p->deg - q->deg;
23 }
24 
25 int mymax(int a, int b) {
26     return a>b ? a:b;
27 }
28 
29 int main() {
30     int i, j, p, exp, deg;
31 
32     while (scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {
33         for (i=0; i<k; ++i)
34             scanf("%d %d", &infos[i].exp, &infos[i].deg);
35 
36         memset(dp, 0, sizeof(dp));
37         qsort(infos, k, sizeof(info_st), comp);
38 
39         for (i=0; i<k; ++i) {
40             exp = infos[i].exp;
41             deg = infos[i].deg;
42             if (i && deg == infos[i-1].deg) {
43                 continue;
44             }
45             for (j=1; j<=s; ++j) {
46                 for (p=deg; p<=m; ++p) {
47                     dp[p][j] = mymax(dp[p][j], dp[p-deg][j-1]+exp);
48                 }
49             }
50         }
51 
52         for (i=1; i<=m; ++i) {
53             if (dp[i][s] >= n)
54                 break;
55         }
56 
57         if (i <= m)
58             printf("%d
", m-i);
59         else
60             printf("-1
");
61     }
62 
63     return 0;
64 }