Problem F Flipping Coins（dp）

Problem FFlipping Coins

Here’s a jolly and simple game: line up a row of N identical coins, all with the heads facingdown onto the table and the tails upwards, and for exactly K times take one of the coins, toss itinto the air, and replace it as it lands either heads-up or heads-down. You may keep all of thecoins that are face-up by the end.

Being, as we established last year, a ruthless capitalist, you have resolved to play optimally towin as many coins as you can. Across all possible combinations of strategies and results, whatis the maximum expected (mean average) amount you can win by playing optimally?

Input

• One line containing two space-separated integers:

– N (1 ≤ N ≤ 400), the number of coins at your mercy;

– K (1 ≤ K ≤ 400), the number of flips you must perform.

Output

Output the expected number of heads you could have at the end, as a real number. The outputmust be accurate to an absolute or relative error of at most 10−6.

题意：

n个数全部反面朝上，k次翻转。

求k次翻转后正面朝上的数学期望。

数学期望（mean）（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。

思路：

1
2
3
4
for(int j=0;j<n;j++){
dp[i+1][j]+=dp[i][j]/2;
dp[i+1][j+1]+=dp[i][j]/2;
}

1
2
dp[i+1][n]+=dp[i][n]/2;
dp[i+1][n-1]+=dp[i][n]/2;

代码：

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<iostream>
#include<cstring>
#include<iomanip>
using namespace std;
double dp[405][405];
//第i次j个正面朝上的期望
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++)
//0-n个正面情况(两种情况,+1,不变)。每次翻反面
{
dp[i+1][j]+=dp[i][j]*0.5;
//不能/2，会舍小数
dp[i+1][j+1]+=dp[i][j]*0.5;
}
dp[i+1][n]+=dp[i][n]*0.5;
//n个正面(-1,不变)
dp[i+1][n-1]+=dp[i][n]*0.5;
}
double sum=0;
for(int i=1;i<=n;i++)
{
sum+=i*dp[k][i];
}
cout<<fixed<<setprecision(6)<<sum<<endl;
return 0;
}

最后

以上就是感性店员最近收集整理的关于Problem F Flipping Coins（dp）的全部内容，更多相关Problem内容请搜索靠谱客的其他文章。