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;

}

巴特西

HDU 3366 Passage （概率DP）

Passage

最新文章

热门文章