<题目链接>
第一行两个整数
接下来一行
个数，第
个数
表示第个烟花被点燃的概率。
输出有两行,第一行表示产生不同颜色的期望个数,第二行表示产生恰好
种颜色的概率,以换行符分割
3 2
0.5 0.25 0.75
1.5000
0.4062
第二问样例解释：
相加得
对于
的数据：
对于
的数据：
输出均保留4位小数,若你的答案误差与std不超过
即为正确
解题分析：
本题是比较经典的dp，dp[i][j]表示前i件物品中产生j件物品的概率，不难想到，状态转移方程为：dp[i][j] = dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i];
意思是：前i件物品中产生j个颜色的概率为前(i-1)个物品产生j个颜色*第i个物品不产生颜色的概率，加上前(i-1)件物品产生(j-1)种颜色*第i个物品产生颜色的概率。然后再用滚动数组优化成一维dp即可。
#include <bits/stdc++.h> using namespace std; const int N = 1e5+10; double p[N]; double dp[1010]; //实际上是dp[i][j]，只不过下面用了滚动数组，意义是前i个物品产生j中颜色的概率 int main(){ int n,k; scanf("%d %d",&n, &k); double ans = 0; for(int i = 1; i <= n; i ++) scanf("%lf",&p[i]), ans += p[i]; dp[0] = 1; for(int i = 1; i <= n; i ++){ for(int j = k;j>=0;j--){ dp[j] = dp[j]*(1-p[i])+dp[j-1]*p[i]; }//前i个物品产生j种颜色的概率为，前i-1个物品产生 j种颜色的概率*第i个物品不产生颜色的概率加上前i-1个物品产生j-1个颜色的概率*第j个物品产生颜色的概率 } printf("%.4f\n%.4lf",ans,dp[k]); return 0; }
2018-09-08
原文：https://www.cnblogs.com/00isok/p/9608211.html