Gym 101606F Flipping Coins(概率dp)

题意：给n枚硬币，初始全部反面向上，有k次机会挑选一枚硬币抛，求正面向上的最大数学期望。

思路：求的是最大数学期望，所以只有两种情况。

1.i<n时，挑选反面向上的硬币抛，朝上朝下的概率都为0.5；

2.i==n时，这时全部都是反面朝上，挑选一枚硬币抛，朝上朝下的概率都为0.5；

这样就可以得出dp方程；

dp[i][j]表示第i次抛，有j枚硬币朝上。

i<n时，dp[i+1][j] += dp[i][j]*0.5;

            dp[i+1][j+1]  += dp[i][j]*0.5;

i==n时,dp[i+1][j]  += dp[i][j]*0.5;

            dp[i+1][j-1]  += dp[i][j]*0.5;

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
double dp[410][410];
int main()
{
int n,k;
cin >> n >> k;
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
for(int i = 0; i < k; i++)
{
for(int j = 0; j < n; j++)
{
dp[i+1][j] += dp[i][j]*0.5;
dp[i+1][j+1] += dp[i][j]*0.5;
}
dp[i+1][n] += dp[i][n]*0.5;
dp[i+1][n-1] += dp[i][n]*0.5;
}
double ans = 0;
for(int i = 1; i <= n; i++)
ans += i*dp[k][i];
printf("%fn",ans);
return 0;
}

最后

以上就是风趣小蝴蝶为你收集整理的Gym 101606F Flipping Coins(概率dp)的全部内容，希望文章能够帮你解决Gym 101606F Flipping Coins(概率dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。