题解

#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define xin(a) scanf("%d", &a)
using namespace std;
const int maxn = 100000 + 5;
double dp[maxn][202];//到i个时已点燃j个;
int main()
{
    double sum=0;
    int n, k, i, j;
    double a[maxn];
    cin>>n>>k;
    for (i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    dp[0][0]=1;
    dp[0][1]=0;
    for(i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]*(1-a[i]);//!!!!!!
        for(int j=1;j<=k; j++)
            dp[i][j]=dp[i-1][j-1]*a[i]+dp[i-1][j]*(1-a[i]);
    }
    printf("%.4f\n%.4f\n",sum,dp[n][k]);
    return 0;
}

解题思路

第一次看到概率dp吼吼
第一问直接相加,第二问用dp解决,dp[i][j]表示到第i个时已经点燃j个的概率,
dp[i][j]=dp[i-1][j-1]×a[i]+dp[i-1][j]×(1-a[i]);
dp[i-1][j-1]×a[i]表示当前烟花点燃的概率,j+1.
dp[i-1][j]×(1-a[i]);表示当前烟花未点燃
特别注意dp[i][0]需要特别处理
(滚动数组什么的..下次一定?)