出题人题解 | #烟花#

原题解链接：https://ac.nowcoder.com/discuss/149980

第一问

由于每个烟花互不相同，因此每种颜色的个数都是1

根据期望的定义: ans $=\sum p_i\ast 1=\sum p_i=\backslash sum\; p\_\{i\}\; *\; 1=\backslash sum\; p\_\{i\}$

第二问

设$f[i][j]f[i][j]$表示前i个烟花，恰好有$jj$个被点燃的概率

转移的时候枚举当前烟花是否被点燃

滚动数组优化

#include <iostream>
using namespace std;
const int maxn = 1e5+10, maxk = 105;
double dp[maxn][maxk], num[maxn];

int main() {
    int n, k;
    double c, ans1, ans2;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        scanf("%lf",&num[i]);
        c *= (1-num[i]);
        ans1 += num[i];
    }
    dp[0][1] = 0;
    dp[1][0] = 1 - num[1];
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            dp[i][j] = dp[i-1][j-1]*num[i] + dp[i-1][j]*(1-num[i]);
        }
    }
    ans2 = dp[n][k];
    printf("%.5lf\n%.5lf\n",ans1+0.00001,ans2+0.00001);
    
    return 0;
}