Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.
His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.
Input
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .
Output
Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.
Sample Input
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05
Sample Output
4
6
dp[ j] 表示在抢劫到钱j时不被抓概率。最后,只要找出满足要求的最大j。
代码及案例显示
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int T,n,total;
double p;
double a[],dp[];
int b[];
int main()
{
cin>>T;
while(T--)
{
total=;
cin>>p>>n;
for(int i=; i<n; i++)
{
cin>>b[i]>>a[i];
total+=b[i];
}
memset(dp,,sizeof(dp));
dp[]=; //没抢到钱时,逃脱的概率为1
for(int i=; i<n; i++)
for(int j=total; j>=a[i]; j--)
{
dp[j]=max(dp[j],dp[j-b[i]]*(-a[i]));
//cout<<d[j]<<" "<<j<<endl;
}
for(int i=total; i>=; i--)
{
if(dp[i]>-p)
{
cout<<i<<endl;
break;
}
}
}
return ;
}
下面是第一组案例的各种抢劫钱数的概率