UKIEPC2017 . Flipping Coins（动态规划）

问题 F: Flipping Coins

时间限制: 1 Sec  内存限制: 128 MB  Special Judge
提交: 129  解决: 58
[提交] [状态] [讨论版] [命题人:admin]

题目描述

Here’s a jolly and simple game: line up a row of N identical coins, all with the heads facing down onto the table and the tails upwards, and for exactly K times take one of the coins, toss it into the air, and replace it as it lands either heads-up or heads-down. You may keep all of the coins that are face-up by the end.
Being, as we established last year, a ruthless capitalist, you have resolved to play optimally to win as many coins as you can. Across all possible combinations of strategies and results, what is the maximum expected (mean average) amount you can win by playing optimally?

输入

•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 the expected number of heads you could have at the end, as a real number. The output must be accurate to an absolute or relative error of at most 10−6.

样例输入

2 1

样例输出

0.5

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 410;
double dp[maxn][maxn];
int main(){
int n, k;
while(~scanf("%d%d", &n, &k)){
memset(dp, 0, sizeof(dp));
double ans = 0;
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]/2;
dp[i+1][j+1] += dp[i][j]/2;
}
dp[i+1][n] += dp[i][n]/2;
dp[i+1][n-1] += dp[i][n]/2;
}
for(int i=1; i<=n; i++) ans += i*dp[k][i];
printf("%.10lfn", ans);
}
}

最后

以上就是发嗲奇异果为你收集整理的UKIEPC2017 . Flipping Coins（动态规划）的全部内容，希望文章能够帮你解决UKIEPC2017 . Flipping Coins（动态规划）所遇到的程序开发问题。

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