参考blog:
http://blog.csdn.net/hellobabygogo3/article/details/7915083
加上一点自己的感悟吧，开始这里楼判了等于0，因为他有可能没去偷钱,所以为零。
因为去偷每一家银行的钱事件是独立的，所以有P(AB)= P(A)P(B);
所以dp初始化为0。
for(int i = sum;i>=0;--i)
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
| #include<cstdio>
#include<cstring>
#define m(a,b) a>b?a:b
using namespace std;
int main()
{
int t,n,m[105];
double dp[10005],pm[105],p;
int sum;
scanf("%d",&t);
while(t--)
{
scanf("%lf%d",&p,&n);
sum = 0;
for(int i = 0;i < n;++i)
{
scanf("%d%lf",&m[i],&pm[i]);
sum += m[i];
}
memset(dp,0,sizeof(dp));
dp[0] = 1;
for(int i = 0;i < n;++i)
{
for(int j = sum;j >= m[i];--j)
{
dp[j] = m(dp[j],dp[j-m[i]] * (1-pm[i]));
}
}
for(int i = sum;i>=0;--i)
{
if(dp[i] > 1-p)
{
printf("%d\n",i);break;
}
}
}
return 0;
}
|
