首页 > 代码库 > HDU 3366 Passage (概率DP)
HDU 3366 Passage (概率DP)
Passage
Problem Description
Bill is a millionaire. But unfortunately he was trapped in a castle. There are only n passages to go out. For any passage i (1<=i<=n), Pi (0<=Pi<=1) denotes the probability that Bill will escape from this castle safely if he chose this passage. Qi (0<=Qi<=1-Pi) denotes the probability that there is a group of guards in this passage. And Bill should give them one million dollars and go back. Otherwise, he will be killed. The probability of this passage had a dead end is 1-Pi-Qi. In this case Bill has to go back. Whenever he came back, he can choose another passage.
We already know that Bill has M million dollars. Help Bill to find out the probability that he can escape from this castle if he chose the optimal strategy.
We already know that Bill has M million dollars. Help Bill to find out the probability that he can escape from this castle if he chose the optimal strategy.
Input
The first line contains an integer T (T<=100) indicating the number of test cases.
The first line of each test case contains two integers n (1<=n<=1000) and M (0<=M<=10).
Then n lines follows, each line contains two float number Pi and Qi.
The first line of each test case contains two integers n (1<=n<=1000) and M (0<=M<=10).
Then n lines follows, each line contains two float number Pi and Qi.
Output
For each test case, print the case number and the answer in a single line.
The answer should be rounded to five digits after the decimal point.
Follow the format of the sample output.
The answer should be rounded to five digits after the decimal point.
Follow the format of the sample output.
Sample Input
3 1 10 0.5 0 2 0 0.3 0.4 0.4 0.5 3 0 0.333 0.234 0.353 0.453 0.342 0.532
Sample Output
Case 1: 0.50000 Case 2: 0.43000 Case 3: 0.51458
Source
“光庭杯”第五届华中北区程序设计邀请赛 暨 WHU第八届程序设计竞赛
解题思路:T组测试数据,一个人困在了城堡中,有n个通道,m百万money ,每个通道能直接逃出去的概率为 P[i] ,遇到士兵的概率为 q[i],遇到士兵得给1百万money,否则会被杀掉,还有 1-p[i]-q[i] 的概率走不通,要回头。问在可以选择的情况下,逃出去的概率是多少?
首先,n个通道要选择哪个先走哪个后走呢?如果暴力是2^n,显然不可取。只需要贪心,选择逃生概率最大的通道,也就是 p[i]/q[i]最大的优先。
解题代码:用 dp[i][j]记录 还剩j次机会,已经走到第i个通道能逃生的概率。
那么当前:
(1)遇到士兵,dp[i+1][j-1]+=dp[i][j]*q[i]
(2)走不通,dp[i+1][j]+=dp[i][j]*( 1-p[i]-q[i] )
(3)直接逃生,答案加上这个概率。
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int maxn=1100; struct route{ double p,q; friend bool operator < (route a,route b){ return a.p/a.q>b.p/b.q; } }r[maxn]; int n,m; double dp[maxn][20]; void input(){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%lf%lf",&r[i].p,&r[i].q); } sort(r,r+n); for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ dp[i][j]=0; } } } double solve(){ double ans=0; dp[0][m]=1; for(int i=0;i<n;i++){ for(int j=m;j>=0;j--){ ans+=dp[i][j]*r[i].p; if(j-1>=0) dp[i+1][j-1]+=dp[i][j]*r[i].q; dp[i+1][j]+=dp[i][j]*(1.0-r[i].p-r[i].q); } } return ans; } int main(){ int t; scanf("%d",&t); for(int i=1;i<=t;i++){ input(); printf("Case %d: %.5lf\n",i,solve()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。