【Gym - 101606F】Flipping Coins（概率dp）

【Gym - 101606F】Flipping Coins（概率dp）

题干：

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?

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 output

must be accurate to an absolute or relative error of at most 10-6.

题目大意：

给出N个硬币(N<=400)，开始均反面朝上。每次挑出其中一个抛，连续抛K次(K<=400)，求正面朝上的最大数学期望。

解题报告：

因为他说了是采取最佳策略，而不是每轮操作都随机选择一个，所以这题可以dp而不是直接算期望。

例：n=2 时的dp转移表格（抛币次数为2）

AC代码：

#include#include#include#include#include

举一反三：

n个正面朝下的硬币，每轮随机挑选一个硬币并上抛让它自由下落，这样进行K轮，问正面朝上的硬币个数的期望是多少？

n个正面朝下的硬币，每轮随机挑选一个硬币并翻转，这样进行K轮，问正面朝上的硬币个数的期望是多少？

答：dp（i，j）表示i次后有j个朝上的概率，因为有j个朝上，所以转移到dp（i+1，j-1）的概率是j/n，另一个转移类似。这种dp的方法不需要太动脑，至于更好的数学方法，推起来还是麻烦的。

n个正面朝下的硬币，每轮随机挑选一个硬币并翻转，进行K轮停止或硬币全部朝上停止，问正面朝上的硬币个数的期望是多少？

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。