首页 > 代码库 > [HDU 2955]Robberies (动态规划)
[HDU 2955]Robberies (动态规划)
题目链接: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元逃跑的最大概率
代码:
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6 7 const int MAX_N = 110; 8 const double EPS = 1e-8; 9 double dp[MAX_N][MAX_N*MAX_N];10 int T,N,m[MAX_N];11 double P,p[MAX_N];12 13 int main(){14 scanf("%d",&T);15 while( T-- ){16 scanf("%lf%d",&P,&N);17 P = 1 - P;18 int summ = 0;19 for(int i=1;i<=N;i++){20 scanf("%d%lf",&m[i],&p[i]);21 p[i] = 1 - p[i];22 summ += m[i];23 }24 //for(int i=0;i<=summ;i++) dp[1][i] = 1;25 dp[0][0] = 1;26 for(int i=1;i<=N;i++){27 for(int j=0;j<=summ;j++){28 if( j-m[i]>=0 ) dp[i][j] = max(dp[i-1][j],dp[i-1][j-m[i]]*p[i]);29 else dp[i][j] = dp[i-1][j];30 }31 }32 int ans = 0;33 for(int i=0;i<=summ;i++){34 // printf("%f\n",dp[N][i]);35 if( P-dp[N][i]<=EPS ){36 // printf("dp[N][i]=%f < P=%f\n",dp[N][i],P);37 ans = i;38 }39 }40 // puts("");41 printf("%d\n",ans);42 }43 return 0;44 }45 46 /*47 348 0.04 349 1 0.0250 2 0.0351 3 0.0552 0.06 353 2 0.0354 2 0.0355 3 0.0556 0.10 357 1 0.0358 2 0.0259 3 0.0560 */
[HDU 2955]Robberies (动态规划)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。