概率dp总结

总结

参考：
https://www.cnblogs.com/hua-dong/p/8166093.html
https://blog.csdn.net/iceprincess_1968/article/details/80157137
https://blog.sengxian.com/algorithms/probability-and-expected-value-dynamic-programming

SPOJ Favorite Dice
题意：甩一个n面的骰子，问每一面都被甩到的次数期望是多少。

dp[i]:已经抛出i面，为使每一面都被抛到，还要抛的期望。
$dp[i]=\frac{i}{n}*(1+dp[i])+\frac{n-i}{n}*(1+dp[i+1])$
化简即可。

SGU 495
题意：n个盒子里装有礼物，m个人随机选择礼物，选完之后将盒子放回.问所有人选中的礼物数的期望。

法一：
m个人是独立的。
对于每个礼物不被人选中的概率为((n-1)/n)^m
那么不被选中的礼物数的期望就是 n*((n-1)/n)^m
所以答案就是 n-n*((n-1)/n)^m;
法二：
dp[i]：第i个人得到礼物的概率
第i个人得到礼物的概率：
假如第i-1个人没有得到礼物，那么i得到礼物的概率和i-1一样。
假如第i-1个人得到了礼物，那么i得到礼物的概率是i-1得到礼物概率减去1/n
$dp[i]=(1-dp[i-1])*dp[i-1]+dp[i-1]*(dp[i-1]-1.0/n);$

Uva12230Crossing Rivers
题目大意：
有个人每天要去公司上班，每次会经过N条河，家和公司的距离为D，默认在陆地的速度为1，
给出N条河的信息，包括起始坐标p，宽度L，以及船的速度v。船会往返在河的两岸，人到达河岸时，
船的位置是随机的（往返中）。问说人达到公司所需要的期望时间。

需要判断的只有过河的时间。而船的位置是随机的，所以：
1，过每条河最坏的情况是t=3*L/v； 即去的时候船刚刚走。
2，过没条河最优的情况是t=L/v； 即去的时候船刚刚来。
3，由于船是均匀发布的，符合线性性质，所以平均下来，过每条河的时间t=2*L/v。

51Nod 1705 七星剑
题意:你要把一把剑从0星升至7星,有n颗宝石供你选择,第i颗宝石的价值是c[i],在炼化第k颗星的时候，用魔法石i将有p(k,i)的机率成功，即炼化后剑上从原有的(k-1)颗星变成k颗星。但是如果失败不但不会多出星来还会丢失los(k,i)颗星(0<=lose(k,i)<=k-1),当然这次使用的魔法石也会被毁坏）。求打造七星剑花费的期望的最小值。

第一想法的状态是：
dp[i][j]:用第j中宝石炼化第i颗星，炼化剩下的星的期望。
于是方程显然。
dp[i][j]=dp[i+1][k]p[i][j]+dp[i-los[i][j]][k](1-p[i][j])+c[j];
然后就发现成环了。逆推就只能用高斯消元了。

所以考虑正推。
dp[i][j]:从第i颗星升级至第j颗星的期望。这样状态就是可加的。
dp[i][j]=min{c+p*dp[i+1][j]+(1-p)*dp[i-los][j]}
不满足条件的就是dp[i-los][j]，但它可以变成dp[i-los][i]+dp[i][j];

注意-1的情况不能在最后判断，因为即使inf也可以更新下一个的值。
注意枚举顺序。
注意：从有i颗星升级成j颗星，当前炼化的是第i+1颗星。

    for(int j=1;j<=m;++j){
        for(int i=j-1;i>=0;--i){
            dp[i][j]=inf;
            for(int k=1;k<=n;++k){
                dp[i][j]=min((c[k]+p[i+1][k]*dp[i+1][j]+(1-p[i+1][k])*dp[i-los[i+1][k]][i])/p[i+1][k],dp[i][j]);//!!
            }
        }
    }

BZOJ3450: Easy
题意：给定一个序列，仅包含'o','x','?'。‘o’代表长度加1，'x'代表长度清0，‘？’位置未确定(即'o'和'x'的概率分别为0.5)。对于一个 ox？ 序列，连续 k 长度会有k^2的收益，求最终得到的序列的期望收益。

dp[i]:长度为i的期望收益.
这题的初始状态和初值好确定：dp[0]=0，而终值就是所求的答案。所以我们顺推计算。
注意码代码时，$ans+=0.5*((dp[i-1]+1)*(dp[i-1]+1)-dp[i-1]*dp[i-1]);$，dp[i-1]+1不可替换成dp[i].如果替换，概率就重复计算了。

    for(int i=1;i<=n;++i){
        if(s[i]=='o') {
            dp[i]=dp[i-1]+1;
            ans+=dp[i]*dp[i]-dp[i-1]*dp[i-1];
        }
        else if(s[i]=='?'){
            dp[i]=0.5*(dp[i-1]+1);
            ans+=0.5*((dp[i-1]+1)*(dp[i-1]+1)-dp[i-1]*dp[i-1]);//!!
        }
        else dp[i]=0;
    }

BZOJ4318: OSU!
给出一个01序列。在这个串中连续的X个1可以贡献X^3 的分数。求期望分数。

和上道题一样，只是x^2的分数变成了x^3的分数。
注释掉的那里注意：长度期望的平方不等于长度平方期望。我们要的是长度期望的平方。立方同理。不过在代码中将$(x+1)^3−x^3=3x^2+3x+1$化简了。

    for(int i=1;i<=n;++i){
        dp[i]=p[i]*(dp[i-1]+1);
    //  dp1[i]=p[i]*(dp[i-1]+1)*(dp[i-1]+1);
        dp1[i]=p[i]*(dp1[i-1]+2*dp[i-1]+1);
        ans+=p[i]*(dp1[i-1]*3+dp[i-1]*3+1);
    }

51Nod 1450
闯关游戏
有N个游戏。玩家可以任意时刻玩任意一个小游戏，且每个游戏可以玩任意多次，一个游戏玩一次是1min。玩家可以多次挑战同一个小游戏，而且系统只会记录玩家多次挑战中的最好成绩。
根据一些统计，一个玩家在任一次玩第i个小游戏时，都会独立的发生以下结果：
* 有（1000 - Xi - Yi）*0.001的概率会挑战失败；
* 有 Xi*0.001 的概率会挑战成功并获得一颗星；
* 有 Yi*0.001 的概率会挑战成功并获得两颗星.
通关条件：1）N个小游戏的系统记录的最好成绩都是成功；2）这N个小游戏的系统记录成绩中的星星总数至少是M颗。
求最优策略下需要花费时间的期望E。

题目上有几个提示：1.采用最优策略(贪心)，2.星的计算只记录最好成绩。
所以我们不能直接设状态为dp[i][j]，表示过前i关，得到j颗星，通关的最小期望时间； 转移是：dp[i][j]=(1+dp[i+1][j+2]*y[i+1]+dp[i+1][j+1]*x[i+1])/(x[i+1]+y[i+1]);
因为如果一关只能不通关或者得一颗星，打再多次也只能得一颗星。而如果是当前已经是两颗星了，打再多次也不能出现一颗星。
所以要单独考虑得到两颗星的情况。用y大的刷星。

int main(){
//  freopen("a.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)   scanf("%lf%lf",&a[i].x,&a[i].y);
    sort(a+1,a+n+1);
    m-=n;
    for(int i=0;i<m;++i) dp[n][i]=inf;
    for(int i=n-1;i>=0;--i){
        double c=a[i+1].x+a[i+1].y;
        for(int j=0;j<m;++j)
            dp[i][j]=min(1000/c+a[i+1].x/c*dp[i+1][j]+a[i+1].y/c*dp[i+1][j+1],1000/a[i+1].y+dp[i+1][j+1]);
        dp[i][m]=1000/c+dp[i+1][m];
    }
    printf("%.8f\n",dp[0][0]);
    return 0;
}

期望 DP 一般来说有它固定的模式，一种模式是直接 DP，定义状态为到终点期望，采用逆序计算得到答案。一种模式是利用期望的线性性质，对贡献分别计算，这种模式一般要求我们求出每种代价的期望使用次数，而每种代价往往体现在 DP 的转移之中。最后的两个例题是典型的分离变量，用期望的线性性质计算答案的例子，如果状态过于巨大，那么就得考虑分离随机变量了。