概率DP

 http://blog.csdn.net/auto_ac/article/details/9907881

Scout YYF I

 POJ - 3744 

题意：起点是1，有n个点有地雷，问顺利通过的概率。

按地雷分段，求每一段踩到雷的概率p，那么1-p就是通过该段的概率，然后乘法原理每段概率相乘。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=2;
struct Matrix{
    int n;
    double m[maxn][maxn];

    void init(int sz){
        n=sz;
        memset(m,0,sizeof(m));
    }
    Matrix(int sz){
        init(sz);
    }
    void setI(){
        for(int i=0;i<n;i++) m[i][i]=1;
    }

    Matrix operator* (const Matrix& a){
        Matrix res(n);
        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    res.m[i][j]+=m[i][k]*a.m[k][j];
        return res;
    }
};
double quickpow(Matrix b,int n){
    Matrix a(2);
    a.setI();
    while(n){
        if(n&1) a=a*b;
        b=b*b;
        n>>=1;
    }
    return 1-a.m[0][0];
}
int x[15];
int main(){
    int n;
    double p;
    x[0]=0;
    while(scanf("%d%lf",&n,&p)!=EOF){
        n++;
        for(int i=1;i<n;i++) scanf("%d",&x[i]);
        sort(x,x+n);
        double ans=1;
        Matrix b(2);
        b.m[0][0]=p;b.m[0][1]=1-p;
        b.m[1][0]=1;
        for(int i=1;i<n;i++){
            //if(x[i]==x[i-1]+1){ans=0;break;}  
            ans*=quickpow(b,x[i]-x[i-1]-1);
        }
        printf("%.7f
",ans);  //!!poj用%f
    }
}

LOOPS

 HDU - 3853 

题意：求从[1,1]走到[r,c]需要的魔力值。三种走法对应不同概率，每一步消耗2魔力值。

#include <bits/stdc++.h>
using namespace std;

const int maxn=1010;
double p[maxn][maxn][3];
double dp[maxn][maxn];

int main(){
    int r,c;
    while(scanf("%d%d",&r,&c)!=EOF){
        for(int i=0;i<r;i++)
            for(int j=0;j<c;j++)
                for(int k=0;k<3;k++)
                    scanf("%lf",&p[i][j][k]);
        r--;c--;
        dp[r][c]=0;
        for(int i=r;i>=0;i--){
            for(int j=c;j>=0;j--){
                if(p[i][j][0]==1||i==r&&j==c) continue;
                dp[i][j]=(p[i][j][1]*dp[i][j+1]+p[i][j][2]*dp[i+1][j]+2)/(1-p[i][j][0]);
            }
        }
        printf("%.3lf
",dp[0][0]);
    }
    return 0;
}

Aeroplane chess

 HDU - 4405 

题意：

#include <bits/stdc++.h>
using namespace std;

const int maxn=100010;
double dp[maxn];
int fly[maxn];

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)&&(n||m)){
        memset(dp,0,sizeof(dp));
        memset(fly,0,sizeof(fly));
        int u,v;
        for(int i=0;i<m;i++){
            scanf("%d%d",&u,&v);
            fly[u]=v;
        }
        for(int i=n-1;i>=0;i--){
            if(fly[i]) dp[i]=dp[fly[i]];
            else{
                for(int j=1;j<=6;j++){
                    if(i+j>=n) dp[i]+=1.0/6*dp[n];
                    else dp[i]+=1.0/6*dp[i+j];
                }
                dp[i]++;
            }
        }
        printf("%.4lf
",dp[0]);
    }
    return 0;
}

Football

 POJ - 3071 

题意：

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=150;
double p[maxn][maxn];
double dp[maxn][maxn];

int main(){
    int n;
    while(scanf("%d",&n)&&n!=-1){
        int num=1<<n;
        for(int i=0;i<num;i++)
            for(int j=0;j<num;j++)
                scanf("%lf",&p[i][j]);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<num;i++) dp[0][i]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<num;j++)
            for(int k=0;k<num;k++){
                if(j>>(i-1)==((k>>(i-1))^1)) dp[i][j]+=dp[i-1][j]*(dp[i-1][k]*p[j][k]);
            }
        }
        int ans=0;
        for(int i=1;i<num;i++){
            if(dp[n][i]>dp[n][ans]) ans=i;
        }
        printf("%d
",ans+1);
    }
    return 0;
}

One Person Game

 ZOJ - 3329 

题意：有三个骰子，分别有k1,k2,k3个面。每次掷骰子，如果三个面分别为a,b,c则分数置0，否则加上三个骰子的分数之和。当分数大于n时结束。求游戏的期望步数。初始分数为0

#include <bits/stdc++.h>
using namespace std;
const int maxn=610;
int n,k1,k2,k3,a,b,c;
double p[66];
double A[maxn],B[maxn];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
        memset(p,0,sizeof(p));
        double p0=1.0/k1/k2/k3;
        for(int i=1;i<=k1;i++)
        for(int j=1;j<=k2;j++)
        for(int k=1;k<=k3;k++){
            if(i!=a||j!=b||k!=c) p[i+j+k]+=p0;
        }
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        for(int i=n;i>=0;i--){
            A[i]=p0;B[i]=1;
            for(int j=1;j<=k1+k2+k3;j++){
                A[i]+=A[i+j]*p[j];
                B[i]+=B[i+j]*p[j];
            }
        }
        printf("%.16lf
",B[0]/(1-A[0]));
    }
}

Bag of mice

 CodeForces - 148D

题意：王子公主抓老鼠。。。公主先抓，每次王子抓完就会随机跑掉一只，谁先抓到白老鼠就获胜。

记忆化搜索

#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#define P pair<int ,int >
using namespace  std;
const int maxn=1010;
int w,b;
map<P ,double >memo;

double win(int w,int b)
{
    if(w<=0) return 0;
    if(b<=0) return 1;
    P args(w,b);
    if(memo.find(args)!=memo.end())
        return memo[args];
    double res=w*1.0/(w+b);
    double temp=b*1.0/(w+b);
    b--;
    temp*=b*1.0/(w+b);
    b--;
    if(temp>1e-10)
    {
        double brun=win(w,b-1)*b*1.0/(w+b);
        double wrun=win(w-1,b)*w*1.0/(w+b);
        res+=temp*(brun+wrun);
    }
    memo[args]=res;
        return res;
}
int main()
{
    cin>>w>>b;
    double ans=win(w,b);
    printf("%.9lf
",ans);
}

Time travel

 HDU - 4418