Passage

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

Case 1: 0.50000
Case 2: 0.43000
Case 3: 0.51458

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）,布布扣,bubuko.com

HDU 3366 Passage （概率DP）

原文：http://blog.csdn.net/a1061747415/article/details/36898703