概率DP入门总结 16题（转）

很早就被概率题和期望题虐得不行了，这次真的不能忍了，怒刷概率dp，学到了很多，都是最基础的，还需日后强化。

下面说一下我个人的总结：

   很多概率题总逃不开用dp转移。

期望题总是倒着推过来的，概率是正着推的，多做题就会理解其中的原因

有些期望题要用到有关概率或期望的常见公式或思想

遇到dp转移方程(组)中有环的，多半逃不出高斯消元（手动和写代码两种）

这套题中还有道树上的dp转移，还用dfs对方程迭代解方程，真是大开眼界了

当然还有与各种算法结合的题，关键还是要学会分析

当公式或计算时有除法时，特别要注意分母是否为零

以下的题都是很常见的简单题或中等题，简单题尽量自行思考，最好不要看题解。

1、POJ 3744 Scout YYF I (简单题)

很裸的状态转移，并用矩阵乘法分段优化，以前也出现过不少这样的题了。

解题报告题意很简单的，很常见的矩阵做法

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[11];
void mult(double a[][2], double b[][2]) {  //矩阵乘法 a = a*b
    int i, j, k;
    double c[2][2] = {0.0};
    for(i = 0; i < 2; i++)
        for(k = 0; k < 2; k++) if(a[i][k] != 0.0) {
            for(j = 0; j < 2; j++)
                c[i][j] += a[i][k] * b[k][j];
        }
    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
            a[i][j] = c[i][j];
}
int n;
double p;
double A[2][2],ans[2][2];
void solve(int n) {   // ans = A^n
    A[0][0] = p; A[0][1] = 1;
    A[1][0] = 1-p ;A[1][1] = 0;
    ans[0][0] = ans[1][1] = 1.0;
    ans[0][1] = ans[1][0] = 0;
    while(n) {
        if(n&1) mult(ans, A);
        mult(A, A);
        n >>= 1;
    }
}

int t;
int main() {
    int i, j;
    while( ~scanf("%d%lf", &n, &p)) {
        for(i = 0; i < n; i++) scanf("%d", &a[i]);
        sort(a, a+n);
        double ret = 1.0;
        solve(a[0]-1);
        ret *= (1-ans[0][0]);
        for(i = 1; i < n; i++) {
               solve(a[i]-a[i-1]-1);
            ret *= (1-ans[0][0]);
        }
        printf("%.7f
", ret);
    }
    return 0;
}

View Code

2、POJ 3071 Football (简单题)

足球赛的淘汰赛问题。问最后胜利的概率最大的球队。每个队的胜率都用dp算一下比较

解题报告

题意：2^n个队进行足球赛，每个队打败另外一个队都有一个概率。
问最后胜利的概率最大的是哪只球队。

概率DP。

设dp[i][j]表示第i场比赛第j个球队胜利的概率。

画图看看就可以得出公式了。

第一轮，(1,2)(3,4)(5,6)``````

很容易算出来。

第二轮的时候。

比如算3胜出的概率。首先是3在第一轮要胜出，同时要打败(1,2)种的胜者，这是全概率公式了。

/*
POJ 3071
题意：2^n个队进行足球赛，每个队打败另外一个队都有一个概率。
问最后胜利的概率最大的是哪只球队。

概率公式，dp算一下就可以了。
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

double dp[8][200];//dp[i][j]表示在第i场比赛中j胜出的概率
double p[200][200];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==-1)break;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<(1<<n);i++)
          for(int j=0;j<(1<<n);j++)
            scanf("%lf",&p[i][j]);
            //cin>>p[i][j];
        for(int i=0;i<(1<<n);i++)dp[0][i]=1;
        for(int i=1;i<=n;i++)//2^n个人要进行n场比赛
        {
            for(int j=0;j<(1<<n);j++)
            {
                int t=j/(1<<(i-1));
                t^=1;
                dp[i][j]=0;
                for(int k=t*(1<<(i-1));k<t*(1<<(i-1))+(1<<(i-1));k++)
                  dp[i][j]+=dp[i-1][j]*dp[i-1][k]*p[j][k];
            }
        }
        int ans;
        double temp=0;
        for(int i=0;i<(1<<n);i++)
        {
            if(dp[n][i]>temp)
            {
                ans=i;
                temp=dp[n][i];
            }
        }
        printf("%d
",ans+1);
    }
    return 0;
}

View Code

3、codeforces 148D Bag of mice (简单题)

抓老鼠问题。记忆化搜索的话不是很难，要写成for循环的那就比较麻烦了

解题报告

题意：

袋子里有w只白鼠和b只黑鼠

龙和公主轮流从袋子里抓老鼠。谁先抓到白色老师谁就赢。
公主每次抓一只老鼠，龙每次抓完一只老鼠之后会有一只老鼠跑出来。
每次抓老鼠和跑出来的老鼠都是随机的。
如果两个人都没有抓到白色老鼠则龙赢。公主先抓。

问公主赢的概率。

解析：

这题选用记忆化搜索还是比较容易的，不容易错，很快能出来，用for循环做的话有点求期望的感觉。

思路在代码中注明

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
double dp[1001][1001];
bool vis[1001][1001];
int w, b;
double dfs(int w, int b) {
    if (w <= 0) return 0; //没有白就输
    if (b <= 0) return 1; //有白球没有黑就赢
    if (vis[w][b]) return dp[w][b];
    vis[w][b] = 1;
    double &ret = dp[w][b];
    ret = w * 1.0 / (w + b);   //摸到白
    if (b >= 2) {               //公主和恐龙都摸到黑
        double tp = b * 1.0 / (w + b);  
        b--;
        tp *= b * 1.0 / (w + b);
        b--;
            //    白的跑了                               黑的跑了
        ret += tp* (w * 1.0 / (w + b) * dfs(w - 1, b) + b * 1.0 / (w + b) * dfs(w, b - 1));
    }
    return ret;
}
int main() {
    scanf("%d%d", &w, &b);
    printf("%.9f
", dfs(w, b));
    return 0;
}

View Code