概率与期望 – Smokey_Days

2018年12月17日2018年12月17日

lp1850 NOIP2016 换教室

一道优$d\acute{u}$秀$li\acute{u}$的期望DP。
简述题意：
原有一个包括$n$个节点的路径，你可以用$m$次操作，每一次操作可以把第$i$个节点从$c_{i}$换到$b_{i}$。
对于每一次操作，有$p_{i}$的概率成功。求最优决策下路径长度的期望。

首先考虑到是稠密图，故考虑用邻接矩阵来处理。不过需要注意读入时应当取较小值，以及每个点到其本身的距离为$0$
首先用$Floyd$预处理出所有点之间的距离。然后我们定义$f_{i,j,k}$表示，当前在决定第$i$个节点，已经使用了$j$次机会，当前选择为$k$时的期望路径长度。
那么我们考虑转移。
对于每一个状态，我们有两种选择：使用机会或者不使用机会。故而我们尝试推理状态转移方程：
首先，如果不使用机会的话，有两种情况可以转移过来，分别是，上一次使用了机会，或者上一次没有使用机会，故：
$$f_{i,j,0}=Min(f_{i-1,j,0}+mp_{c_{i-1},c_{i}},$$
$$f_{i-1,j,1}+mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}));$$
如果在这个点使用机会且成功的话，则有：
$$f_{i,j-1,1}=Min(f_{i-1,j-1,0}+mp_{c_{i-1},d_{i}}*p_{i}+mp_{c_{i-1},c_{i}}*(1-p_{i}),$$
$$f_{i-1,j-1,1}+m(p_{d_{i-1},d_{i}}*p_{i-1}+mp_{c_{i-1},d_{i}}*(1-p_{i-1}))*p_{i}+$$
$$(mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}))*(1-p_{i});$$
然后，只需要走到终点即可，因此:
$$ Ans=Min(f_{N,i,j})\ (i\in [0,M],j\in [0,1])$$

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int mp[305][305],N,M,V,E;
int c[2005],d[2005];
double p[2005],f[2005][2005][2];
void init(){
    memset(mp,0x3f,sizeof(mp));
    scanf("%d%d%d%d",&N,&M,&V,&E);
    for(int i=1;i<=N;++i){
        scanf("%d",&c[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%d",&d[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%lf",&p[i]);
    }
    int u,v,w;
    for(int i=1;i<=E;++i){
        scanf("%d%d%d",&u,&v,&w);
        mp[u][v]=Min(mp[u][v],w),mp[v][u]=Min(mp[u][v],w);
    }
    for(int i=1;i<=V;++i){
        mp[i][i]=0;
    }
    for(int k=1;k<=V;++k){
        for(int i=1;i<=V;++i){
            for(int j=1;j<=V;++j){
                mp[i][j]=Min(mp[i][j],mp[i][k]+mp[k][j]); 
            }
        }
    }
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<=1;++k){
                f[i][j][k]=1000007;
            }
        }
    }
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=N;++i){
        for(int j=0;j<=M;++j){
            f[i][j][0]=Min(f[i-1][j][0]+mp[c[i-1]][c[i]],f[i-1][j][1]+mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]));
            if(!j){
                continue;
            }
            f[i][j][1]=Min(f[i-1][j-1][0]+mp[c[i-1]][d[i]]*p[i]+mp[c[i-1]][c[i]]*(1-p[i]),f[i-1][j-1][1]+(mp[d[i-1]][d[i]]*p[i-1]+mp[c[i-1]][d[i]]*(1-p[i-1]))*p[i]+(mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]))*(1-p[i]));
        }
    }
    double ans=1000007;
    for(int i=0;i<=M;++i){
        for(int j=0;j<2;++j){
            ans=Min(ans,f[N][i][j]);
        }
    }
    /*
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<2;++k){
                printf("%.2lf ",f[i][j][k]);
            }
            printf("|");
        }
        puts("");
    }
    */
    printf("%.2lf",ans);
}
int main(){
    init();
    return 0;
}

2018年10月30日2019年1月4日

lp1654 OSU!

真是棒到不行!OSU!

首先，我们可以知道，对于长度为$x$的线段，在其后加上一个新的长度为1的线段，新线段的价值是$(x+1)^3$
那么，价值的差便是：
$$3*x^2+3*x+1$$
而这样的贡献必须要当前点被选中才可行的。似乎可以得到：
$$f_{i}=f_{i-1}*(1-p_{i})+(f_{i-1}^3+3*f_{i-1}^2+3*f_{i-1}+1)*p_{i}$$
但仔细观察就可以发现这样显然是错误的。
这是因为，平方的期望不等于期望的平方。
因此，对于平方的期望，以及一次方的期望，我们应当另外维护两个函数$g,u$，分别表示平方的期望和一次方的期望。
那么：
$$g_{i}=(g_{i-1}+2*u_{i-1}+1)*p_{i}$$
$$u_{i}=(u_{i-1}+1)*p_{i}$$
于是：
$$f_{i}=f_{i-1}+(3*g_{i-1}+3*u_{i-1}+1)*p_{i}$$
问题得解。
这一题还是很有思维难度的。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
double p[100005],u[100005],g[100005],f[100005];
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf",&p[i]);
    }
    u[0]=g[0]=f[0]=0;
    double ans=0;
    for(int i=1;i<=n;++i){
        u[i]=(u[i-1]+1)*p[i];
        g[i]=(g[i-1]+2*u[i-1]+1)*p[i];
        f[i]=f[i-1]+(3*g[i-1]+3*u[i-1]+1)*p[i];
        ans+=f[i];
    }
    printf("%.1lf",f[n]);
    
}
int main(){
    init();
    return 0;
}

2018年10月30日

CF148D Bag of mice

看到$w,b \le 1000$，我们可以大胆猜想复杂度是$w*b$的（大雾）
那么我们设$f[i][j]$表示，包里还剩下$i$只白老鼠，$j$只黑老鼠的时候，轮到公主抽，赢的期望。
仔细看了看题意（之前题意看错了，瞎想半天，淦。），我们可以发现，公主输会发生在两种情况下：
一：包里没有白老鼠了；二：公主抽到了黑老鼠而龙抽到了白老鼠。
同时，对于一个局面，公主胜利的概率有两部分；
一：公主抽到了白球。二：公主的状态转移到的状态抽到了白球。
我们分类讨论。
首先，依据公主抽到白球的概率是$\frac{i}{i+j}$，我们可以知道：
$$f_{i,j}+=\frac{i}{i+j}$$
然后，用填表法，我们发现，公主抽到了黑老鼠且龙抽到黑老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}$$
在这种情况下，跑出一只白老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}$$
跑出一只黑老鼠的概率是：
$$\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
所以得到转移方程：
$$f_{i,j}=\frac{j}{i+j}*\frac{j-1}{i+j-1}+f_{i-1,j-2}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{i}{i+j-2}+$$
$$f_{i,j-3}*\frac{j}{i+j}*\frac{j-1}{i+j-1}*\frac{j-2}{i+j-2}$$
于是填表法可得解。

#include<iostream>
#include<cstdio>
using namespace std;
int w,b;
double f[1005][1005];
void init(){
    scanf("%d%d",&w,&b);
    for(int i=1;i<=w;++i){
        for(int j=1;j<=b;++j){
            f[i][j]=0;
        }
    }
    for(int i=1;i<=w;++i){
        f[i][0]=1;
    }
    for(int i=1;i<=b;++i){
        f[0][i]=0;
    }
    for(int i=1;i<=w;++i){
        for(int j=1;j<=b;++j){
            f[i][j]+=(double)i/(i+j);
            if(j>=2){
                f[i][j]+=f[i-1][j-2]*(double)j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2);
            }
            if(j>=3){
                f[i][j]+=f[i][j-3]*(double)j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2);
            }
        }
    }
    printf("%.9lf",f[w][b]);
}
int main(){
    init();
    return 0;
}

2018年10月30日2018年10月30日

sp1026 Favorite Dice

开始学习期望DP。
这是一道期望DP入门题。
首先我们设$f[i]$表示，已经取了$i$种数，距离取完的期望回合数。
根据概率的基本定理，我们可以知道，已经取了$k$种以后，下一种取到的是未取到过的概率是$\frac{n-k}{n} $；而取到的是取过的概率是$\frac{k}{n}$
我们很容易可以知道，已经取了$i$种数，下一次取可能有两种情况：
一：取到的是一种新的数。
二：取到的是已经取到过的数。
但无论如何都要再取一次才有造成状态改变的空间。
故而我们得到方程：
$$ f_{i}=\frac{n-i}{n}*f_{i+1}+\frac{i}{n}*f_{i}+1 $$
即：
$$ n*f_{i}=(n-i)*f_{i+1}+i*f_{i}+n $$
从而得到：
$$ f_{i}=\frac{(n-i)*f_{i+1}+n}{n-i} $$
等价于：
$$ f_{i}=f_{i+1}+\frac{n}{n-i} $$
于是我们得到了逆向的递推方程。
然后是边界条件。很显然，$f_{n}=0$，这是因为，已经取到$n$种以后，就意味着已经取完了。

#include<iostream>
#include<cstdio>
using namespace std;
double f[1005];
int n;
void init(){
    scanf("%d",&n);
    f[n]=0;
    for(int i=n-1;i>=0;--i){
        f[i]=f[i+1]+(double)n/(n-i);
    }
    printf("%.2lf\n",f[0]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

分类：概率与期望

lp5104 红包发红包

lp1850 NOIP2016 换教室

lp1654 OSU!

CF148D Bag of mice

sp1026 Favorite Dice