【HDOJ】2602 Bone Collector

DP。
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 
 5 typedef struct {
 6     int val, vol;
 7 } bone_st;
 8 
 9 bone_st bones[1005];
10 int dp[1005];
11 
12 int comp(const void *a, const void *b) {
13     bone_st *p = (bone_st *)a;
14     bone_st *q = (bone_st *)b;
15     if (p->vol == q->vol)
16         return q->val - p->val;
17     else
18         return p->vol - q->vol;
19 }
20 
21 int main() {
22     int case_n, n, v;
23     int i, j, k;
24 
25     scanf("%d", &case_n);
26 
27     while (case_n--) {
28         scanf("%d %d", &n, &v);
29         for (i=0; i<n; ++i)
30             scanf("%d", &bones[i].val);
31         for (i=0; i<n; ++i)
32             scanf("%d", &bones[i].vol);
33 
34         qsort(bones, n, sizeof(bone_st), comp);
35         memset(dp, 0, sizeof(dp));
36 
37         for (i=0; i<n; ++i) {
38             if (bones[i].vol > v)
39                 break;
40             k = bones[i].val;
41             for (j=v; j>=bones[i].vol; --j) {
42                 if (k+dp[j-bones[i].vol] > dp[j])
43                     dp[j] = k + dp[j-bones[i].vol];
44             }
45         }
46         printf("%d
", dp[v]);
47     }
48 
49     return 0;
50 }