概率DP – hahaschool

POJ 3744 Scout YYF I

April 08, 20152015-04-08hahaschoolOne Comment

题意

某人在直线上走，直线上有若干格子，起点是1号格，每次这个人都有p概率走1格，1-p概率走二格，有一些格子有地雷，走上去就被爆了，所以要你求你能安全走到终点（可以看成是站在n+1号格）上概率。

思路

每一个格子的概率都可以通过它前两个的格子的概率推出来，这样的话跟斐波那契很像。
联想我们想快速地搞出来一个非常大的fib值的方法是什么？快速幂。
所以这个题我们用快速幂来做。

dp方程其实都不叫dp，叫递推，大概长这个样子：

$\begin{bmatrix}p&1-p\\1&0 \end{bmatrix}\begin{bmatrix}p_{n} \\ p_{n-1}\end{bmatrix}=\begin{bmatrix} p_{n+1}\\p_{n}\end{bmatrix}$

直接矩阵乘法模版＋快速幂就行。

处理地雷的话，你就先走到地雷那里，停一下，把地雷格的dp值抹成0，然后继续往下走，走到下一个地雷，最后走到终点。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

const int N = 2;
int n;

struct Mat {
    double mat[N][N];
};
Mat operator * (Mat a, Mat b) {
    Mat c;
    memset(c.mat, 0, sizeof(c.mat));
    int i, j, k;
    for(k = 0; k < N; ++k) {
        for(i = 0; i < N; ++i) {
            for(j = 0; j < N; ++j) {
                c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
            }
        }
    }
    return c;
}
Mat operator ^ (Mat a, int k) {
    Mat c;
    int i, j;
    for(i = 0; i < N; ++i)
        for(j = 0; j < N; ++j)
            c.mat[i][j] = (i == j);    //初始化为单位矩阵

    for(; k; k >>= 1) {
        if(k&1) c = c*a;

        a = a*a;
    }
    return c;
}


int main(){
    while(cin >> n){
        double p = 0;
        cin >> p;
        vector<double> mine;
        mine.push_back(0);
        for(int i = 1;i <= n;i++){
            int tmp = 0;
            cin >> tmp;
            mine.push_back(tmp);
        }
        sort(mine.begin(),mine.end());
        Mat a,b;
        double dn = 1;
        for(int i = 1;i < mine.size();i++){
            a.mat[0][0] = p;
            a.mat[0][1] = 1-p;
            a.mat[1][0] = 1;
            a.mat[1][1] = 0;
            Mat c = a^(mine[i]-mine[i-1]);
            b.mat[0][0] = 0;
            b.mat[0][1] = 0;
            b.mat[1][0] = dn;
            b.mat[1][1] = 0;
            Mat d = c * b;
            dn = d.mat[1][0];
        }
        printf("%.7f\n",dn);
    }


    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

const int N = 2;

int n;

struct Mat {

double mat[N][N];

};

Mat operator * (Mat a, Mat b) {

Mat c;

memset(c.mat, 0, sizeof(c.mat));

int i, j, k;

for(k = 0; k < N; ++k) {

for(i = 0; i < N; ++i) {

for(j = 0; j < N; ++j) {

c.mat[i][j] += a.mat[i][k] * b.mat[k][j];

}

return c;

}

Mat operator ^ (Mat a, int k) {

Mat c;

int i, j;

for(i = 0; i < N; ++i)

for(j = 0; j < N; ++j)

c.mat[i][j] = (i == j); //初始化为单位矩阵

for(; k; k >>= 1) {

if(k&1) c = c*a;

a = a*a;

}

return c;

}

int main(){

while(cin >> n){

double p = 0;

cin >> p;

vector<double> mine;

mine.push_back(0);

for(int i = 1;i <= n;i++){

int tmp = 0;

cin >> tmp;

mine.push_back(tmp);

}

sort(mine.begin(),mine.end());

Mat a,b;

double dn = 1;

for(int i = 1;i < mine.size();i++){

a.mat[0][0] = p;

a.mat[0][1] = 1-p;

a.mat[1][0] = 1;

a.mat[1][1] = 0;

Mat c = a^(mine[i]-mine[i-1]);

b.mat[0][0] = 0;

b.mat[0][1] = 0;

b.mat[1][0] = dn;

b.mat[1][1] = 0;

Mat d = c * b;

dn = d.mat[1][0];

}

printf("%.7f\n",dn);

}

return 0;

}

HDU 4405 Aeroplane chess

April 08, 20152015-04-08hahaschoolLeave a comment

题意

玩线性飞行棋，一共有n个格子，每一次扔骰子，扔几点走几格，如果踩到了跳跃格，就跳过去，而且可以连续跳跃，走到或冲过终点游戏就胜利。问你扔多少次骰子之后游戏胜利（求期望）。

思路

很直接的概率dp题，加上了跳跃，不过因为我们的方向始终如一，所以没有成环的悲剧发生，可以很轻松的解出来。
我们设dp[i]表示位于第i格时，完成游戏需要的扔骰子数目,那么我们有：

$dp[i]=\sum_{k=1}^{6}(\frac{1}{6}dp[i+k])+1$

对于a to b的跳跃关系，我们又有：

$dp[a]=dp[b]$

这样dp方程就推好了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int fly[100010];
double dp[100010];

int flyme(int i){
    if (fly[i]) {
        return fly[i] = flyme(fly[i]);
    }else{
        return i;
    }

}

int main(){
    int n = 0,m = 0;
    while (scanf(" %d %d",&n,&m)) {
        if (!(n+m)) {
            break;
        }
        memset(dp, 0, sizeof(dp));
        memset(fly, 0, sizeof(fly));
        for (int i = 1; i <= m; i++) {
            int from = 0,to = 0;
            scanf(" %d %d",&from,&to);
            fly[from] = to;
        }
        for (int i = n-1; i >= 0;i--) {
            for (int j = 1; j <= 6; j++) {
                dp[i] += dp[flyme(i+j)]/6;
            }
            dp[i]++;
        }
        printf("%.4lf\n",dp[0]);
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

int fly[100010];

double dp[100010];

int flyme(int i){

if (fly[i]) {

return fly[i] = flyme(fly[i]);

}else{

return i;

}

int main(){

int n = 0,m = 0;

while (scanf(" %d %d",&n,&m)) {

if (!(n+m)) {

break;

}

memset(dp, 0, sizeof(dp));

memset(fly, 0, sizeof(fly));

for (int i = 1; i <= m; i++) {

int from = 0,to = 0;

scanf(" %d %d",&from,&to);

fly[from] = to;

}

for (int i = n-1; i >= 0;i--) {

for (int j = 1; j <= 6; j++) {

dp[i] += dp[flyme(i+j)]/6;

}

dp[i]++;

}

printf("%.4lf\n",dp[0]);

}

return 0;

}

POJ 2096 Collecting Bugs

April 07, 20152015-04-07hahaschoolLeave a comment

题意

给软件挑bug，每天挑出来一个，每个bug都有两个属性：分类和子系统，这两个属性都是完全随机的，已知一共有n个分类，s个子系统，问你挑出的bug完全覆盖全部分类和子系统需要多长时间（求期望）。

思路

优惠券问题的变种，相当于升高到了二维，因此dp数组也要开成二维。

我们设定dp[i][j]表示距离完成任务还有i个分类j个子系统没有覆盖，状态的转移用如下几种：
1.挑出的bug属于全新的分类和子系统
2.挑出的bug仅仅属于全新的分类
3.挑出的bug仅仅属于全新的子系统
4.挑出的bug没有任何新意
这样，我们可以得出状态转移方程： $dp[i][j]=\frac{i}{n}\frac{j}{s}dp[i-1][j-1]+\frac{n-i}{n}\frac{j}{s}dp[i][j-1]+\frac{i}{n}\frac{n-j}{s}dp[i-1][j]+\frac{n-i}{n}\frac{n-j}{s}dp[i][j]+1$

经过化简可以发现这是个很直接的递推方程了，所以可以很轻松的出答案了。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

double dp[1010][1010];

int main(){
    int in = 0,im = 0;
    while (cin >> in >> im) {
        double n = in,m = im;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0;
        for (int ii = 1; ii <= in; ii++) {
            double i = ii;
            dp[ii][0] = dp[ii-1][0] + n/i;
        }
        for (int ii = 1; ii <= im; ii++) {
            double i = ii;
            dp[0][ii] = dp[0][ii-1] + m/i;
        }
        for (int ii = 1; ii <= in; ii++) {
            for (int ij = 1; ij <= im; ij++) {
                double i = ii,j = ij;
                dp[ii][ij] = (i*j)*dp[ii-1][ij-1]+(n-i)*j*dp[ii][ij-1]+i*(m-j)*dp[ii-1][ij]+m*n;
                dp[ii][ij] /= m*n-(n-i)*(m-j);
            }
        }
        printf("%.4lf\n",dp[in][im]);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

double dp[1010][1010];

int main(){

int in = 0,im = 0;

while (cin >> in >> im) {

double n = in,m = im;

memset(dp, 0, sizeof(dp));

dp[0][0] = 0;

for (int ii = 1; ii <= in; ii++) {

double i = ii;

dp[ii][0] = dp[ii-1][0] + n/i;

}

for (int ii = 1; ii <= im; ii++) {

double i = ii;

dp[0][ii] = dp[0][ii-1] + m/i;

}

for (int ii = 1; ii <= in; ii++) {

for (int ij = 1; ij <= im; ij++) {

double i = ii,j = ij;

dp[ii][ij] = (i*j)*dp[ii-1][ij-1]+(n-i)*j*dp[ii][ij-1]+i*(m-j)*dp[ii-1][ij]+m*n;

dp[ii][ij] /= m*n-(n-i)*(m-j);

}

printf("%.4lf\n",dp[in][im]);

}

return 0;

}

HDU 4035 Maze

April 06, 20152015-04-06hahaschoolLeave a comment

题意

一个人被丢进了迷宫，迷宫有n个房间，1号房间作为起点，房间之间以隧道联通，任意两个房间的通路只有一条，每进入一个房间，有k的概率被干掉，然后在1号房间复活，有e的概率直接脱出迷宫，若上述两事件未发生，则这个人会从当前房间的全部隧道中随便选一个进去（即使沿着刚才的路返回）。问你这个人要穿过多少隧道才能拖出迷宫（求期望）。

思路

注意审题，“任意两个房间的通路只有一条” ，这句话告诉我们迷宫可以抽象为一棵树（因为没有环，起点确定所以看作树根），又因为是求期望，所以这是一个树上进行的概率dp。
对于每个节点，我们定义dp数组为dp[i]表示在i号房间脱出迷宫的期望穿洞数。
接下来就是处理dp方程，如果你可以写出来dp方程的话，你会发现这个方程有两种版本，一种是叶子节点，一种是普通节点（其实还有一种根节点，不过这个只是最后出答案用的），列完之后我们会发现dp方程组成环，而且每一个方程式都有着类似的未知项（或者说是格式统一），面对这种情况就可以归纳出方程的一般形式，建立几个系数数组，回代一般形式，确定出系数数组的递推关系式，化环为链。这种情形经常出现在概率dp问题中。
最后需要注意本题有坑点：判断误解的时候，需要直接判断1-A[1](这个是什么请看下面的数学推导）的绝对值是否非常小（分母趋向于0），在这里卡精度，你至少需要1e-9的精度。在这里用其他的方法判断一律是过不了的～

代码

//
//  HDU4035.cpp
//  playground
//
//  Created by Adam Chang on 2015/4/5.
//  Copyright (c) 2015年 Adam Chang. All rights reserved.
//
//Review: Each pair of rooms is connected by one and only one path
//this statement marks the structure is tree (or DAG),i.e. no rings.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

struct vertexType{
    vector<int> to;
    double pk,pe;
    void init(){
        to.clear();
        pk = 0;
        pe = 0;
    }
} vertex[10005];

double A[10005],B[10005],C[10005];
bool vis[10005];
void dfs(int father){
    vis[father] = true;
    vector<int> child;
    for (int i = 0; i < vertex[father].to.size(); i++) {
        int next = vertex[father].to[i];
        if (vis[next]) {
            continue;
        }
        child.push_back(next);
        dfs(next);
    }

    double w = 1-vertex[father].pk-vertex[father].pe;
    if (child.size()) {
        //normal vertex
        double m = (double)vertex[father].to.size();
        double q = 1;
        double e = vertex[father].pk;
        double r = w;
        for (int i = 0; i < child.size(); i++) {
            e += w/m*A[child[i]];
            q -= w/m*B[child[i]];
            r += w/m*C[child[i]];
        }
        A[father] = e/q;
        B[father] = w/m/q;
        C[father] = r/q;
    }else{
        //endpoint vertex
        A[father] = vertex[father].pk;
        B[father] = w;
        C[father] = w;
    }
}


int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for (int ci = 1; ci <= caseCnt; ci++) {
        int n = 0;
        scanf(" %d",&n);
        for (int i = 1; i <= n; i++) {
            vertex[i].init();
        }
        for (int i = 1; i <= n-1; i++) {
            int arg1,arg2;
            scanf(" %d %d",&arg1,&arg2);
            vertex[arg1].to.push_back(arg2);
            vertex[arg2].to.push_back(arg1);
        }
        for (int i = 1; i <= n; i++) {
            double arg1,arg2;
            scanf(" %lf %lf",&arg1,&arg2);
            vertex[i].pk = arg1/100;
            vertex[i].pe = arg2/100;
        }
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        memset(C, 0, sizeof(C));
        memset(vis, 0, sizeof(vis));
        dfs(1);
        if (abs(1-A[1]) < 0.000000001) {//这里卡精度
            printf("Case %d: impossible\n",ci);
            continue;
        }
        printf("Case %d: %.10lf\n",ci,C[1]/(1-A[1]));
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

// HDU4035.cpp

// playground

// Created by Adam Chang on 2015/4/5.

//Review: Each pair of rooms is connected by one and only one path

//this statement marks the structure is tree (or DAG),i.e. no rings.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

struct vertexType{

vector<int> to;

double pk,pe;

void init(){

to.clear();

pk = 0;

pe = 0;

}

} vertex[10005];

double A[10005],B[10005],C[10005];

bool vis[10005];

void dfs(int father){

vis[father] = true;

vector<int> child;

for (int i = 0; i < vertex[father].to.size(); i++) {

int next = vertex[father].to[i];

if (vis[next]) {

continue;

}

child.push_back(next);

dfs(next);

}

double w = 1-vertex[father].pk-vertex[father].pe;

if (child.size()) {

//normal vertex

double m = (double)vertex[father].to.size();

double q = 1;

double e = vertex[father].pk;

double r = w;

for (int i = 0; i < child.size(); i++) {

e += w/m*A[child[i]];

q -= w/m*B[child[i]];

r += w/m*C[child[i]];

}

A[father] = e/q;

B[father] = w/m/q;

C[father] = r/q;

}else{

//endpoint vertex

A[father] = vertex[father].pk;

B[father] = w;

C[father] = w;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for (int ci = 1; ci <= caseCnt; ci++) {

int n = 0;

scanf(" %d",&n);

for (int i = 1; i <= n; i++) {

vertex[i].init();

}

for (int i = 1; i <= n-1; i++) {

int arg1,arg2;

scanf(" %d %d",&arg1,&arg2);

vertex[arg1].to.push_back(arg2);

vertex[arg2].to.push_back(arg1);

}

for (int i = 1; i <= n; i++) {

double arg1,arg2;

scanf(" %lf %lf",&arg1,&arg2);

vertex[i].pk = arg1/100;

vertex[i].pe = arg2/100;

}

memset(A, 0, sizeof(A));

memset(B, 0, sizeof(B));

memset(C, 0, sizeof(C));

memset(vis, 0, sizeof(vis));

dfs(1);

if (abs(1-A[1]) < 0.000000001) {//这里卡精度

printf("Case %d: impossible\n",ci);

continue;

}

printf("Case %d: %.10lf\n",ci,C[1]/(1-A[1]));

}

return 0;

}

Tag: 概率DP

POJ 3744 Scout YYF I

题意

思路

代码

HDU 4405 Aeroplane chess

题意

思路

代码

POJ 2096 Collecting Bugs

题意

思路

代码

HDU 4035 Maze

题意

思路

相关数学推导

代码