概率/期望DP_牛客博客

初步认识一下概率DP，写题的时候发现概率DP和概率论关系还蛮大的嗳（废话

最近学习面向对象的时候发现很多还没接触过的东西，数据结构倒还好。。

LOOPS

VJ链接：https://vjudge.net/problem/HDU-3853

思路：注意分母为0的情况

int n,m;
double c1[MAXN][MAXN];//i+1
double c2[MAXN][MAXN];//j+1
double c3[MAXN][MAXN];//
double dp[MAXN][MAXN];
//dp[i][j]=c3*(dp[i][j]+2)+c2*(dp[i][j+1]+2)+c3*(dp[i+1][j]+2);//注意题目中是2magic啊
//dp[i][j]=c3*dp[i][j]+c2*dp[i][j+2]++c3*dp[i+1][j]+2；
//dp[i][j]=(c2*dp[i][j+2]++c3*dp[i+1][j]+2)/(1-c3);
int main()
{
    while(~s2(n,m))
    {
        mem(dp,0);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%lf %lf %lf",&c3[i][j],&c2[i][j],&c1[i][j]);
        for(int i=n;i>=1;i--)
        {
            for(int j=m;j>=1;j--)
            {
                if(i==n&&j==m) continue;
                if(fabs(1-c3[i][j])<EPS) continue;
                dp[i][j]=(c2[i][j]*dp[i][j+1]+c1[i][j]*dp[i+1][j]+2)/(1-c3[i][j]);
            }
        }
        printf("%.3lf\n",dp[1][1]);
    }
    //stop;
    return 0;
}

Check the difficulty of problems

VJ链接：https://vjudge.net/problem/POJ-2151

思路：没思路

题意要求每个队至少一题且至少有一个队过题数大于n的概率

发现“至少一个题”“至少一个队这些条件，应该想到使用容斥原理。

用s[i][j]表示i队最后最多过j题的概率，s1为每个队至少过1题的概率，s2为每个队过题数量在1~n-1的概率

那么s1=(1-s[ 1 ][ 0 ])*.....(1-s[ i ][ 0 ])*(1-s[ t ][ 0 ])，s2=( t 项相乘) (s[ i ][ n-1]-s[ i ][ 0 ]);

ans=s1-s2;

通过一个数组求前缀和计算 s 数组，

于是设计dp[i][j][k],通过递推计算dp[ i ][ m ][ k ]，对 dp[ i ][ m ][ k ]求前缀和即为s数组；

临界条件即为0题的时候。

//思路我感觉不能更对了呜呜呜，可是代码WA掉了

佛了，调了半天结果是POJ不支持lf输出，从G++改成C++就过了，又是血的教训。。

//dp[i][j][k]，i队在前j题解出k题概率
//dp[i][j][k]=dp[i][j-1][k]*(1-p[i][j])+dp[i][j-1][k-1]*p[i][j];
//边界dp[i][0][0]=1;dp[i][j][0]通过递推求出
//s[i][k]表示i最多解决k道概率，对dp[i][j][m]前缀和
//s1表示所有队伍至少解决一道题
//s1=(1-s[i][0])*(...)
//s2表示所有队伍解决问题在1~n-1之间的概率
//s2=(s[1][N-1]-s[1][0])*(s[2][N-1]-s[2][0])*```;
//ans=s1-s2;
int m,t,n;//问题数量队伍数量至少解决问题
double s[MAXN][35];
double p[MAXN][35];
double dp[MAXN][35][35];
int main()
{
    while(s3(m,t,n)&&(n+m+t))
    {
        for(int i=1;i<=t;i++)
            for(int j=1;j<=m;j++)
                scanf("%lf",&p[i][j]);
        mem(dp,0);mem(s,0);
        for(int i=1;i<=t;i++)
        {
            dp[i][0][0]=1.0;
            for(int j=1;j<=m;j++) //
                dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j]);

            for(int j=1;j<=m;j++)
                for(int k=1;k<=j;k++)
                    dp[i][j][k]=dp[i][j-1][k-1]*p[i][j]+dp[i][j-1][k]*(1-p[i][j]);
            
            s[i][0]=dp[i][m][0];//s[i][j]通过dp[i][m]求得
            for(int k=1;k<=m;k++) 
                s[i][k]=s[i][k-1]+dp[i][m][k];
        }
        double s1=1.0,s2=1.0;
        for(int i=1;i<=t;i++)
        {
            s1*=(s[i][m]-s[i][0]);
            s2*=(s[i][n-1]-s[i][0]);
        }
        printf("%.3lf\n",s1-s2);
    }
    //stop;
    return 0;
}

Bag of mice（记忆化搜索，DP，假概率DP）

VJ链接：https://vjudge.net/problem/CodeForces-148D

题意：w白老鼠，b黑老鼠，公主龙轮流拿老鼠，但是龙拿出老鼠的时候会吓出来一直老鼠，只有公主拿到老鼠公主胜，求公主胜利的概率

思路：读完题之后，由数据范围，应该想到使用记忆化搜索，于是：

//记忆化搜索
int w,b;
double vis[MAXN][MAXN][2];//
double dfs(int x,int y,int who)
{
    if(who==0)
    {
        if(x==0) return 0;
        if(y==0) return 1;
        if(vis[x][y][0]) return vis[x][y][0];
        return vis[x][y][0]=x*1.0/(x + y) + y*1.0/(x+y)*dfs(x, y - 1, 1);
    }
    else
    {
        if(x==0||y==0) return 0;
        if(vis[x][y][1]) return vis[x][y][1];
        return vis[x][y][1] = y*1.0/(x+y)*( (y >= 2 ? (y*1.0 - 1)/(x+y - 1)*dfs(x, y - 2, 0):0) + x*1.0/(x+y- 1)*dfs(x - 1, y - 1, 0));
    }
    
}
int main()
{
    while(~s2(w,b))
    {
        mem(vis,0);
        double ans=dfs(w,b,0);
        printf("%.9lf\n",ans);
    }
    //stop;
    return 0;
}

但.....是这是个DP啊摔(′д｀ )…彡…彡，老师上课讲如果写不出DP转移方程就先想一想暴搜是怎么搜的，，，

通过暴搜我们已经发现抓老鼠抓到第几轮和答案是没有关系的，公主赢的概率只和当前白色黑色老鼠个数，而且不同子状态之间不影响。

于是：

//dp[i][j]到某轮白色老鼠为i，黑色老鼠为j公主赢的概率
//事件        dp值                 发生概率
//公主抓白：   1;         i/(i+j)
//龙抓到白：   0;         j/(i+j)*i/(i+j-1)
//跳出白：dp[i-1][j-2];   j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)
//跳出黑：dp[i][j-3];     j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)
//dp[i][0]=1,dp[0][j]=0;
int w,b;//
double dp[MAXN][MAXN];
int main()
{
    while(~s2(w,b))
    {
        mem(dp,0);
        for(int i=1;i<=w;i++) dp[i][0]=1;
        //for(int i=1;i<=b;i++) dp[0][i]=0;
        for(int i=1;i<=w;i++)
        {
            for(int j=1;j<=b;j++)
            {
                dp[i][j]+=(double)i/(i+j);
                if(j>=2) dp[i][j]+=((double)j/(i+j))*((double)(j-1)/(i+j-1))*((double)i/(i+j-2))*dp[i-1][j-2];
                if(j>=3) dp[i][j]+=(double)j/(i+j)*((double)(j-1)/(i+j-1))*((double)(j-2)/(i+j-2))*dp[i][j-3];
            }
        }
        printf("%.9lf\n",dp[w][b]);
    }
    //stop;
    return 0;
}

Football （完全二叉树）

VJ链接：https://vjudge.net/problem/POJ-3071

求所有足球队中获胜概率最大的球队。

和上一题不同，这题比赛到第几轮与概率计算有关，

同时两个球队晋级一个球队，应该从中看出这是一个完全二叉树 ，

新知识：二叉树中右移操作能找出父节点，异或操作能找出兄弟节点

此题中，为判断j,k在i层相遇（在第i层成为兄弟节点），求出j,k在i-1层的父亲节点编号，判断他们在i-1层的节点的父亲节点能否成为兄弟。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=150;
double p[maxn][maxn];
double dp[maxn][maxn];
int main()
{
    int n;
    while(cin>>n&&(n+1))
    {
        int m=(1<<n);
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                scanf("%lf",&p[i][j]);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<m;i++)
            dp[0][i]=1;
        for(int i=1;i<=n;i++)
            for(int j=0;j<m;j++)
                for(int k=0;k<m;k++)
                    if((j>>(i-1)^1)==(k>>(i-1)))
                        dp[i][j]+=dp[i-1][j]*dp[i-1][k]*p[j][k];

        int ans=0;
        for(int i=0;i<m;i++)
            if(dp[n][i]>dp[n][ans])
                ans=i;
        cout<<ans+1<<endl;
    }
    return 0;
}

概率/期望DP

LOOPS

Check the difficulty of problems

Bag of mice（记忆化搜索，DP，假概率DP）

Football （完全二叉树）