有一个小偷要偷银行的钱,可是他偷每家银行总是有一定的概率被抓,现在给了你一个概率P,只要他被抓的概率乘积不大与P,他就是安全的。问你在他安全的情况下,他最多可以偷多少钱。
首先给定一个数T,表示的是有T组数据,每组数据首先给出一个小数p和一个整数n,分别表示的是最大的能够被抓住的概率,如果>这个概率这个强盗的母亲就不让他去,然后下面有n行数据,每行有两个数,分别表示这个银行的钱数和被抓住的概率。
思路
典型的0-1背包问题
本题特殊点在于浮点数不好遍历,于是转成所有银行的总资产为背包容量V,求最大的逃跑概率。
题目中给的是被抓的概率,所以求逃跑概率为1-p[i]
。
状态转移方程:dp[j] = max(dp[j], dp[j - bank[i].Mj] * bank[i].Pj)
。
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std;
const int MAXN = 1e4 + 5;
double dp[MAXN];
struct node{ int Mj; double Pj; } bank[105];
int main(){ int T; scanf("%d", &T); while(T--){ int n, sum; double p; scanf("%lf%d", &p, &n); p = 1.0 - p; sum = 0; for (int i = 0; i < n; i++){ scanf("%d%lf", &bank[i].Mj, &bank[i].Pj); bank[i].Pj = 1.0 - bank[i].Pj; sum += bank[i].Mj; } memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 0; i < n; i++){ for (int j = sum; j >= bank[i].Mj; j--){ dp[j] = max(dp[j], dp[j - bank[i].Mj] * bank[i].Pj); } } for (int i = sum; i >= 0; i--){ if(dp[i]-p>0.000000001){ printf("%d\n", i); break; } } } return 0; }
|