【HDOJ】1963 Investment

完全背包。
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define max(a, b) (a>b) ? a:b
 5 
 6 int val[15], an[15];
 7 int dp[50000];
 8 
 9 int main() {
10     int case_n;
11     int n, m, year;
12     int i, j, k;
13 
14     scanf("%d", &case_n);
15 
16     while (case_n--) {
17         scanf("%d %d", &m, &year);
18         scanf("%d", &n);
19         for (i=1; i<=n; ++i) {
20             scanf("%d %d", &val[i], &an[i]);
21             val[i] /= 1000;
22         }
23         for (k=1; k<=year; ++k) {
24             memset(dp, 0, sizeof(dp));
25             for (i=1; i<=n; ++i) {
26                 for (j=val[i]; j<=m/1000; ++j)
27                     dp[j] = max(dp[j], dp[j-val[i]]+an[i]);
28             }
29             //printf("%dyear:%d
", k, dp[m/1000]);
30             m += dp[m/1000];
31         }
32         printf("%d
", m);
33     }
34 
35     return 0;
36 }