Posted on 2010-12-13 12:04
小小菜鸟蛋 阅读(522)
评论(0) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://acm.hdu.edu.cn/showproblem.php?pid=2955dp[i] 表示偷了 i 块钱时不被抓的概率
dp[j] = max(dp[j], dp[j - m[i]] * (1 - p[i]))
(注意：因为是概率事件，在抢了第一家银行后不被抓的情况下再去抢第二家银行，所以要 *（1-p[i]）而不是 + )
01 #include <cstdio>
02 #include <cstring>
03 using namespace std;
04
05 const int N = 110;
06 double dp[N*N], p[N];
07 int m[N];
08 int t, n;
09 double P;
10
11 double max(double a, double b)
12 {
13 return a > b ? a : b;
14 }
15
16 int main()
17 {
18 for (scanf("%d", &t); t; t--)
19 {
20 scanf("%lf%d", &P, &n);
21 P = 1 - P;
22 int sum = 0;
23 for (int i = 1; i <= n; i++)
24 {
25 scanf("%d%lf", &m[i], &p[i]);
26 sum += m[i];
27 }
28 memset (dp, 0, sizeof(dp));
29 dp[0] = 1; //不偷钱则绝对不会被抓
30 for (int i = 1; i <= n; i++)
31 for (int j = sum; j >= m[i]; j--)
32 dp[j] = max(dp[j], dp[j-m[i]] * (1 - p[i]));
33 for (int i = sum; i >= 0; i--)
34 if (dp[i] >= P)
35 {
36 printf("%d\n", i);
37 break;
38 }
39 }
40 }