牛客NC18200烟花

总时间限制: 1000ms
内存限制: 262144K

题目描述

小a有n个烟花，每个烟花代表着互不相同的颜色，对于第i个烟花，它有p_i的概率点燃，现在小a要去点燃它们，他想知道产生颜色的期望个数及产生恰好产生k种颜色的概率

输入格式:

第一行两个整数n,k.接下来一行n个数，第i个数p_i表示第i个烟花被点燃的概率

输出格式:

输出有两行
第一行表示产生不同颜色的期望个数
第二行表示产生恰好k种颜色的概率
以换行符分割

样例输入

3 2
0.5 0.25 0.75

样例输出

1.5000
0.4062

来源

牛客网

#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 = 10000 + 5;

double dp[maxn][maxn];//到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]需要特别处理