LibreOJ #6191. 「美团 CodeM 复赛」配对游戏

二次联通门 : LibreOJ #6191. 「美团 CodeM 复赛」配对游戏

/*
    LibreOJ #6191. 「美团 CodeM 复赛」配对游戏

    概率dp

*/
#include <cstdio>
#include <iostream>

const int BUF = 12312312;
char Buf[BUF], *buf = Buf;

inline void read (int &now)
{
    for (now = 0; !isdigit (*buf); ++ buf);
    for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf);
}

#define Max 3212
double dp[Max][Max];

int Main ()
{
    fread (buf, 1, BUF, stdin);
    int N; read (N); register int i, j;
    for (i = 0; i <= N; ++ i)
        dp[0][i] = i;
    for (i = 1; i <= N; ++ i)
    {
        dp[i][0] = (dp[i - 1][0] + 1 + dp[i - 1][1]) * 0.5;
        for (j = 1; j <= N; ++ j)
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) * 0.5;
    }
    printf ("%.3lf", dp[N][0]);
    return 0;
}
int ZlycerQan = Main ();
int main (int argc, char *argv[]) {;}