首页 > 代码库 > [HDU 2955]Robberies (动态规划)

[HDU 2955]Robberies (动态规划)

2024-07-27 19:56:20   221人阅读

题目链接：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 (动态规划)


联系
我们