Gym 101606 F-Flipping Coins（概率dp）

题意
有n个硬币排成一排，开始的时候所有的硬币都是正面朝下，你必须要扔K次硬币，每次选择一个硬币，如果你采取最优策略，K次以后朝上的硬币数的最大期望是多少？

随机变量X是指朝上的硬币数，当有N枚硬币的时候，X=0，1，2，3....N

E(X)=1*p(1)+2*p(2)+....+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求期望就好了~

复制代码#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #define MAX 505 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; double dp[MAX][MAX]; int main() { int n,k,i,j; scanf("%d%d",&n,&k); dp[0][0]=1; for(i=1;i<=k;i++){ for(j=0;j<=n;j++){ if(j<n){ dp[i][j]+=dp[i-1][j]*0.5; dp[i][j+1]+=dp[i-1][j]*0.5; } else{ dp[i][j]+=dp[i-1][j]*0.5; dp[i][j-1]+=dp[i-1][j]*0.5; } } } double ans=0; for(i=1;i<=n;i++){ ans+=i*dp[k][i]; } printf("%.8fn",ans); 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
32
33
34
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define MAX 505
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
double dp[MAX][MAX];
int main()
{
int n,k,i,j;
scanf("%d%d",&n,&k);
dp[0][0]=1;
for(i=1;i<=k;i++){
for(j=0;j<=n;j++){
if(j<n){
dp[i][j]+=dp[i-1][j]*0.5;
dp[i][j+1]+=dp[i-1][j]*0.5;
}
else{
dp[i][j]+=dp[i-1][j]*0.5;
dp[i][j-1]+=dp[i-1][j]*0.5;
}
}
}
double ans=0;
for(i=1;i<=n;i++){
ans+=i*dp[k][i];
}
printf("%.8fn",ans);
return 0;
}