首页 > 其他 > 详细

【HDOJ】2955 Robberies

时间:2014-05-29 12:57:55      阅读:414      评论:0      收藏:0      [点我收藏+]

01背包。将最大金额作为容量v。概率做乘法。

bubuko.com,布布扣
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define mymax(a, b) (a>b) ? a:b
 5 
 6 float dp[10005];
 7 int mon[105];
 8 float fs[105];
 9 
10 int main() {
11     int case_n;
12     float ff, f;
13     int m, v;
14     int i, j;
15 
16     scanf("%d", &case_n);
17 
18     while (case_n--) {
19         scanf("%f %d", &ff, &m);
20         v = 0;
21         for (i=1; i<=m; ++i) {
22             scanf("%d %f", &mon[i], &fs[i]);
23             fs[i] = 1 - fs[i];
24             v += mon[i];
25         }
26         ff = 1 - ff;
27         memset(dp, 0, sizeof(dp));
28         dp[0] = 1;
29         for (i=1; i<=m; ++i) {
30             for (j=v; j>=mon[i]; --j) {
31                 dp[j] = mymax(dp[j], dp[j-mon[i]]*fs[i]);
32             }
33             /*
34             for (j=0; j<=v; ++j) {
35                 printf("%f ", dp[j]);
36             }
37             printf("\n");
38             */
39         }
40         for (i=v; i>0; --i)
41             if (dp[i] >= ff)
42                 break;
43         printf("%d\n", i);
44     }
45 
46     return 0;
47 }
bubuko.com,布布扣

 

【HDOJ】2955 Robberies,布布扣,bubuko.com

【HDOJ】2955 Robberies

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

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