首页 > 代码库 > 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.
 

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.
 

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.
 

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;
}