Flipping Coins

トランスファゲート
変換元:https://www.cnblogs.com/LQLlulu/p/8886855.html(このブログは本当に気が抜けている)
n個の硬貨が一列に並んでいて、最初はすべての硬貨が正面から下を向いています.K回の硬貨を投げなければなりません.毎回1つの硬貨を選んで、K回以降の上向きの硬貨数の最大の期待はいくらですか.
考え方:期待値が最大の場合、正面から下を向くコインを選択するたびに
————————————————————————————————————————————————
ランダム変数Xとは、上向きの硬貨の数である、N枚の硬貨がある場合、X=0、1、2、3…である.N
E(X)=1*p(1)+2*p(2)+....+n*p(n).
最大の期待を求めるには、コインを投げるときに、できるだけ正面から下を向いたコインを投げる戦略に従います.
現在0からn-1枚の硬貨が正面を向いている場合は、正面を向いている硬貨を選んで投げることができ、投げ終わったら上を向いて硬貨の数が変わらないか+1
現在n枚のコインが正面を向いている場合は、正面を向いているコインを選んで投げるしかありません.投げ終わったら上を向いているコインの数は変わらないか-1
————————————————————————————————————————————————
dp[i][j]をi回投げた後にj枚の硬貨が上向く確率とする
上にまとめた法則に基づいて,我々は状態への移行方程式を行うことができる.
j
dp[i+1][j]+=dp[i][j]*0.5
dp[i+1][j+1]+=dp[i][j]*0.5
j=nのとき
dp[i+1][j+1]+=dp[i][j]*0.5
dp[i+1][j-1]+=dp[i][j]*0.5
このように確率を渡して後でjを遍歴して期待を求めればいいのです~
コードは次のとおりです.

#include 
#define pre(i,x,nn) for(int i=x;i<=nn;i++)
#define ll long long
using namespace std;
int n,k;
int main()
{
    scanf("%d%d",&n,&k);
    double dp[500][500]={0};
    dp[0][0]=1;
    for(int i=0;i