Educational DP Contest : I – Coins 题解

主要思路

概率 DP,显然地。

我们怎么来统计呢?在存下概率之后,我们枚举轮数并且枚举硬币向上的情况,之后转移即可,代码里一目了然。

代码

// I.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3030;
int n;
double prob[MAX_N], dp[MAX_N][MAX_N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &prob[i]);
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= i; j++)
        {
            int x = j, y = i - j;
            if (x)
                dp[x][y] += dp[x - 1][y] * prob[i];
            if (y)
                dp[x][y] += dp[x][y - 1] * (1 - prob[i]);
        }
    double ans = 0;
    for (int i = 0; n - i > i; i++)
        ans += dp[n - i][i];
    printf("%.10lf", ans);
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注