首页 > 其他 > 详细

【HDOJ】3732 Ahui Writes Word

时间:2014-09-18 18:17:44      阅读:185      评论:0      收藏:0      [点我收藏+]

初看01背包,果断TLE。是因为n和C都比较大。但是vi和ci却很小,转化为多重背包。

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 int map[15][15];
 5 int dp[10005];
 6 int n, C;
 7 
 8 int max(int a, int b) {
 9     return a>b ? a:b;
10 }
11 
12 void ZeroOnePack(int v, int c) {
13     for (int i=C; i>=c; --i)
14         dp[i] = max(dp[i-c]+v, dp[i]);
15 }
16 
17 void CompeletePack(int v, int c) {
18     for (int i=c; i<=C; ++i)
19         dp[i] = max(dp[i-c]+v, dp[i]);
20 }
21 
22 void MultiPack(int v, int c, int k) {
23     if (c*k >= C) {
24         CompeletePack(v, c);
25         return ;
26     }
27     int r = 1;
28     while (r < k) {
29         ZeroOnePack(r*v, r*c);
30         k = k - r;
31         r <<= 1;
32     }
33     ZeroOnePack(k*v, k*c);
34 }
35 
36 int main() {
37     int v, c;
38     char s[15];
39     int i, j;
40 
41     while (scanf("%d %d", &n, &C) != EOF) {
42         memset(map, 0, sizeof(map));
43         memset(dp, 0, sizeof(dp));
44         for (i=0; i<n; ++i) {
45             scanf("%s %d %d", s, &v, &c);
46             map[v][c]++;
47         }
48         for (i=1; i<=10; ++i) {
49             for (j=0; j<=10; ++j) {
50                 if (map[i][j])
51                     MultiPack(i, j, map[i][j]);
52             }
53         }
54         printf("%d\n", dp[C]);
55     }
56 
57     return 0;
58 }

 

【HDOJ】3732 Ahui Writes Word

原文:http://www.cnblogs.com/bombe1013/p/3979485.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!