GYM 101606 F.Flipping Coins（概率DP）

63 阅读 0 评论 42 点赞

我是靠谱客的博主任性战斗机，最近开发中收集的这篇文章主要介绍GYM 101606 F.Flipping Coins（概率DP），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

初始有 n n 枚硬币反面朝上排成一排， $k$ 次操作，每次选取一枚硬币掷向空中，该枚硬币落下后正面朝上和反面朝上的概率均为 0.5 0.5 ，问采取最优方案的情况下， k k 次操作后正面朝上的硬币数量期望最大值

Input

两个整数 $n, k (1 \leq n, k \leq 400)$

Output

输出 k k 次操作后正面朝上硬币数量期望最大值

Sample Input

2 1

Sample Output

0.5

Solution

$d p [i] [j]$ 表示操作 j j 次有 $i$ 枚硬币朝上的概率

若 i<n i < n ，那么显然第 j+1 j + 1 次操作要掷一枚反面朝上的硬币，此时有 0.5 0.5 概率多一枚正面朝上硬币， 0.5 0.5 概率没有多，故有转移

dp[i+1][j+1]+=0.5⋅dp[i][j],dp[i][j+1]+=0.5⋅dp[i][j] d p [ i + 1 ] [ j + 1 ] + = 0.5 ⋅ d p [ i ] [ j ] , d p [ i ] [ j + 1 ] + = 0.5 ⋅ d p [ i ] [ j ]

若 i=n i = n ，那么第 j+1 j + 1 次操作只能选择掷一枚正面朝上的硬币，同理有转移

dp[i−1][j+1]+=0.5⋅dp[i][j],dp[i][j+1]+=0.5⋅dp[i][j] d p [ i − 1 ] [ j + 1 ] + = 0.5 ⋅ d p [ i ] [ j ] , d p [ i ] [ j + 1 ] + = 0.5 ⋅ d p [ i ] [ j ]

∑i=1ni⋅dp[i][k] ∑ i = 1 n i ⋅ d p [ i ] [ k ] 即为 k k 次操作后正面朝上硬币数量期望最大值，时间复杂度 $o (n k)$

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=405;
double dp[maxn][maxn];
int n,k;
int main()
{
while(~scanf("%d%d",&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++)
{
if(j<n)dp[i+1][j]+=0.5*dp[i][j],dp[i+1][j+1]+=0.5*dp[i][j];
else dp[i+1][j-1]+=0.5*dp[i][j],dp[i+1][j]+=0.5*dp[i][j];
}
double ans=0;
for(int i=0;i<=n;i++)ans+=i*dp[k][i];
printf("%.9fn",ans);
}
return 0;
}