Gym 101606F - Flipping Coins - [概率DP]

题目链接:https://codeforc.es/gym/101606/problem/F

题解:

假设 $f[i][j]$ 表示抛 $i$ 次硬币,有 $j$ 个硬币正面朝上的概率。

所以只有两种挑选硬币的情况:

  1.正面硬币数量为 $[0,n-1]$,选择反面硬币抛,则正面硬币数量比原本增加 $1$ 或者不变。

  2.正面硬币数量为 $n$,随便选择一个硬币抛,则正面硬币数量比原本减少 $1$ 或者不变。

因此可得状态转移方程:

对于 $j<n$,有 f[i+][j+]+=f[i][j]*0.5, f[i+][j]+=f[i][j]*0.5;

对于 $j=n$,有 f[i+][n]+=f[i][n]*0.5, f[i+][n-]+=f[i][n]*0.5;

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int MAX=;
int n,k;
double f[MAX][MAX];
int main()
{
cin>>n>>k;
f[][]=;
for(int i=;i<k;i++)
{
for(int j=;j<n;j++)
{
f[i+][j]+=f[i][j]*0.5;
f[i+][j+]+=f[i][j]*0.5;
}
f[i+][n]+=f[i][n]*0.5;
f[i+][n-]+=f[i][n]*0.5;
}
double ans=;
for(int j=;j<=n;j++) ans+=f[k][j]*j;
printf("%.8f\n",ans);
}

(好吧,只能说概率和期望我是真的不会做……)

上一篇:ML学习分享系列(2)_计算广告小窥[中]


下一篇:Css简介