UPC-7027: Flipping Coins (DP)

7027: Flipping Coins

时间限制: 1 Sec  内存限制: 128 MB  Special Judge
提交: 127  解决: 56
[提交] [状态] [讨论版] [命题人: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>
using namespace std;
#define IO
ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define rep(i,j,k)
for(int i=j;i<k;i++)
#define per(i,j,k)
for(int i=j;i<=k;i++)
const int maxn = 500;
double dp[maxn][maxn];
int n,k;
void init()
{
// memset(dp,0,sizeof(dp));
dp[0][0]=1;
//绗?娆℃姇涓€瀹氬彧鏈夊弽闈?
for(int i=1;i<=n;i++)
dp[0][i] = 0;
//绗?娆℃姇鍑虹幇i>=1涓闈㈢殑姒傜巼涓?
for(int i=0;i<=k;i++)
{
for(int j=0;j<=n;j++)
{
dp[i+1][j]+= dp[i][j]/2;
if(j!=n) dp[i+1][j+1]+= dp[i][j]/2;
else
dp[i+1][j-1] += dp[i][j]/2;
//n涓潰閮芥闈㈡椂锛屽彧鏈変繚瀛樹笉鍙樻垨鑰?1锛?
}
}
}
int main(void)
{
cin>>n>>k;
init();
double ans=0;
for(int i=1;i<=n;i++)
ans += dp[k][i]*i
;
//????祝?i?????母??
printf("%.7lfn",ans);
}
/**************************************************************
Problem: 7027
User: St064
Language: C++
Result: 正确
Time:0 ms
Memory:3648 kb
****************************************************************/

最后

以上就是生动小兔子为你收集整理的UPC-7027: Flipping Coins (DP)的全部内容，希望文章能够帮你解决UPC-7027: Flipping Coins (DP)所遇到的程序开发问题。

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