AtCoder Educational DP Contest I - Coins 题解

题意

有nn枚硬币，第ii枚硬币有pip_i的概率正面朝上，有1−pi1-p_i的概率反面朝上。
扔完所有硬币，求正面朝上的银币数比反面朝上的银币数多的概率。

思路

是一道期望dp的入门题，其实比起dp把他叫做递推更合适。

状态设计

这道题的状态设计需要仔细思考，将状态f[i][j]f[i][j]设为前ii个硬币中有jj个以上正面朝上的硬币显然不好，转移过于复杂。
于是我们考虑将状态设计为前ii个硬币中正好有jj个正面朝上的硬币，最后再将f[n][⌈n+1⌉2]f[n][\frac{\lceil n+1 \rceil}{2}]至f[n][n]f[n][n]的值累加起来即可。

转移方程

那状态转移方程如何编写呢？一个硬币ii的状态一定只有两种可能，有pip_i的概率正面朝上，1−pi1-p_i的概率反面朝上。
要让前ii个硬币里有正好jj个正面朝上，也就有两种可能：

  • 前i−1i-1个硬币里有j−1j-1个正面朝上，并且第ii个正面朝上，概率为f[i−1][j−1]×p[i]f[i-1][j-1]\times p[i]；
  • 前i−1i-1个硬币里已经有jj个正面朝上，此时第ii个只能反面朝上，概率为f[i−1][j]×(1−p[i])f[i-1][j]\times (1-p[i])。

初始状态

现在状态和状态转移方程我们都设计好了，来考虑初始状态的值。
我们转移的时候总会用到f[i−1][j]f[i-1][j]和f[i−1][j−1]f[i-1][j-1]，所以我们需要把每一项f[i][0]f[i][0]都设置好。显然前00个硬币里有00个正面朝上的概率是1，后面的f[i][0]f[i][0]自然就等于f[i−1][0]×(1−p[i])f[i-1][0]\times (1-p[i])，因为所有硬币都必须反面朝上。
到这里题目我们就做完了，要注意精度的问题。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
ld p[3005];
ld ans[3005][3005];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){cin>>p[i];}
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)   ans[i][j] = 0.00;
    }
    ans[0][0] = 1;
    for(int i=1;i<=n;i++){
        ans[i][0] = ans[i-1][0]*(1-p[i]);
        for(int j=1;j<=i;j++){
            ans[i][j] = ans[i-1][j-1]*p[i]+ans[i-1][j]*(1-p[i]);
            // if(ans[i][j]>0.00)cout<<i<<" "<<j<<" "<<ans[i][j]<<"\n";
        }
    }
    ld sum = 0;
    for(int i=(n+1)/2;i<=n;i++){
        sum+=ans[n][i];
    }
    cout<<fixed<<setprecision(10)<<sum;
    return 0;
}