题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2955
题意是给你一个概率P，和N个银行
现在要去偷钱，在每个银行可以偷到m块钱，但是有p的概率被抓
问你被抓的概率在P以下，最多能偷多少钱。
刚开始我还在想，A银行被抓的概率是a，B银行被抓的概率是b，那么偷A和B被抓的概率是a*b。。
傻逼了- -。。a*b是既被A银行抓又被B银行抓。。
所以用逃跑的概率计算
dp[i][j]代表从前i个银行里偷了j元逃跑的最大概率
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std; const int MAX_N = ;
const double EPS = 1e-;
double dp[MAX_N][MAX_N*MAX_N];
int T,N,m[MAX_N];
double P,p[MAX_N]; int main(){
scanf("%d",&T);
while( T-- ){
scanf("%lf%d",&P,&N);
P = - P;
int summ = ;
for(int i=;i<=N;i++){
scanf("%d%lf",&m[i],&p[i]);
p[i] = - p[i];
summ += m[i];
}
//for(int i=0;i<=summ;i++) dp[1][i] = 1;
dp[][] = ;
for(int i=;i<=N;i++){
for(int j=;j<=summ;j++){
if( j-m[i]>= ) dp[i][j] = max(dp[i-][j],dp[i-][j-m[i]]*p[i]);
else dp[i][j] = dp[i-][j];
}
}
int ans = ;
for(int i=;i<=summ;i++){
// printf("%f\n",dp[N][i]);
if( P-dp[N][i]<=EPS ){
// printf("dp[N][i]=%f < P=%f\n",dp[N][i],P);
ans = i;
}
}
// puts("");
printf("%d\n",ans);
}
return ;
} /*
3
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
*/