Gym 101606F Flipping Coins [ 递推 DP ]

题意：有n个硬币，排成一排，抛k次，一开始都是反面朝上，问正面朝上硬币的期望。

思路：全程懵逼啊。。。。。

----------------------------------------------------------------------------------------------------------------------

随机变量X是指正面朝上的硬币的个数， 概率为p(X); X = 0, 1, 2, 3, 4, ......, n;

E(X) = 1*p(1) +2*p(2) + 3*p(3)+....+n*p(n);

要想求最大期望，我们在扔硬币的时候最好是尽量扔正面朝下的硬币；  

如果当前有0到n - 1枚硬币正面朝上，我们可以选择正面朝下的硬币来扔，扔完以后朝上的硬币数不变或者+1；

如果当前有n枚硬币正面朝上，我们只能选择正面朝上的硬币来扔，扔完以后朝上的硬币数不变或者-1；

 ---------------------------------------------------------------------------------------------------------------------

令dp[ i ][ j ]为扔i次以后 j枚硬币朝上的概率；

根据上面总结的规律，我们可以得到的状态转移方程：

当 j < n 时： 

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

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

当j = n 时：

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

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

这样递推出概率来以后遍历一遍 j 求期望就可以了。。

代码：

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=400+10;
int n, k;
double dp[N][N], ans = 0;
int main(){
//freopen("in.txt","r",stdin);
while(~scanf("%d%d", &n,&k))
{
ans = 0;
memset(dp, 0, sizeof(dp)); dp[0][0] = 1.0;
for(int i = 0; i < k; i++)
{
for(int j = 0; j < n; j++)
dp[i+1][j] += dp[i][j]*0.5,
//j < n扔完以后朝上的硬币数不变；
dp[i+1][j+1] += dp[i][j]*0.5;
//j < n扔完以后朝上的硬币数 +1；
dp[i + 1][n] += dp[i][n]*0.5;
//j = n扔完以后朝上的硬币数不变；
dp[i + 1][n - 1] += dp[i][n]*0.5;
//j = n扔完以后朝上的硬币数 -1；
}
for(int i=1;i<=n;i++) ans += dp[k][i]*i; //E(X) = 1*P(1) + 2*p(2)+...+n*P(n);
printf("%.6lfn", ans);
}
return 0;
}

最后

以上就是动人小鸭子最近收集整理的关于Gym 101606F Flipping Coins [ 递推 DP ]的全部内容，更多相关Gym内容请搜索靠谱客的其他文章。