LightOj_1079 Just another Robbery

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MAXN 10010
20 #define MOD 1000000007
21 #define eps 1e-6
22 double dp[MAXN];
23 int w[MAXN];
24 double v[MAXN];
25 int n;
26 double p; 
27 void show(int V)
28 {
29     for(int i = 0; i <= V; i ++)
30         printf(dp[i] == INF? "INF ," : "%.3lf ,", dp[i]);
31     printf("\n");
32 }
33 void ZeroOnePack(int V, int n)
34 {
35     fill(dp, dp + V + 1, 0);
36 
37     dp[0] = 1.0;
38     for(int i = 0; i < n; i ++)
39         for(int j = V; j >= w[i]; j --)
40             dp[j] = max(dp[j], dp[j - w[i]] * (1 - v[i]));
41 }
42 
43 int main()
44 {
45     int T;
46     int kcase = 0;
47     scanf("%d", &T);
48     while(T --)
49     {
50         int V = 0;
51         scanf("%lf %d", &p, &n);
52         for(int i = 0; i < n; i ++)
53         {
54             scanf("%d %lf", &w[i], &v[i]);
55             V += w[i];
56         }
57         ZeroOnePack(V, n);
58         int ans = 0;
59         for(int i = 0 ; i <= V; i ++)
60             if(dp[i] > (1 - p))
61                 ans = max(ans, i);
62         printf("Case %d: %d\n", ++ kcase, ans);
63     }
64     return 0;
65 }