hdu 2955 Robberies(01背包)

01背包的变形，因为概率P为浮点数所以不能作为背包容量，只能找能抢的最大金额作为容量。刚开始还傻傻地想求最小被抓的概率，但是细想被抓只有一次，所以只能求最大逃跑概率。

View Code

 1 /*
 2 Author:Zhaofa Fang
 3 Lang:C++
 4 */
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <sstream>
 8 #include <iostream>
 9 #include <cmath>
10 #include <cstring>
11 #include <algorithm>
12 #include <string>
13 #include <utility>
14 #include <vector>
15 #include <queue>
16 #include <stack>
17 #include <map>
18 #include <set>
19 
20 using namespace std;
21 
22 typedef long long ll;
23 #define DEBUG(x) cout<< #x << ':' << x << endl
24 #define PII pair<int,int>
25 #define PB push_back
26 #define MP make_pair
27 #define FI first
28 #define SE second
29 #define lowbit(x) (x&(-x))
30 #define INF (1<<30)
31 
32 int m[105];
33 double p[105];
34 double dp[10005];
35 int main()
36 {
37     #ifndef ONLINE_JUDGE
38     freopen("in","r",stdin);
39     #endif
40     int T;
41     cin>>T;
42     while(T--)
43     {
44         double P;
45         int n;
46         scanf("%lf%d",&P,&n);
47         int M=0;
48         for(int i=1;i<=n;i++)scanf("%d%lf",&m[i],&p[i]),M+=m[i];
49         for(int i=1;i<=M;i++)dp[i] = 0;
50         dp[0] = 1;
51         for(int i=1;i<=n;i++)
52         {
53             for(int j=M;j>=m[i];j--)
54             {
55                 dp[j] = max(dp[j],dp[j-m[i]]*(1-p[i]));
56             }
57         }
58         int ans = 0;
59         for(int i=M;i>=0;i--)
60         {
61             if(P>=(1-dp[i]))
62             {
63 
64                 ans = i;
65                 break;
66             }
67         }
68         printf("%d\n",ans);
69     }
70     return 0;
71 }