[nk] 牛客练习赛26 B-烟花 概率dp+滚动数组

前言

传送门 :

题意

给定 n n n个烟花,每个烟花有 p [ i ] p[i] p[i]的概率点燃,每个烟花颜色都不一样

询问能产生的颜色期望个数, 以及产生 k k k 个颜色的概率

思路

对于第一问 : 期望个数

E ( X ) = ∑ 1 ∗ p ( x ) E(X)=\sum1*p(x) E(X)=∑1∗p(x)

第二问我们考虑使用 动态规划

状态表示 : f [ i ] [ j ] f[i][j] f[i][j]表示前 i i i个烟花被点燃 j j j个的概率

状态转移 : f [ i ] [ j ] = f [ i − 1 ] [ j ] ∗ ( 1 − p [ i ] ) + f [ i − 1 ] [ j − 1 ] ∗ p [ i ] f[i][j]=f[i-1][j]*(1-p[i])+f[i-1][j-1]*p[i] f[i][j]=f[i−1][j]∗(1−p[i])+f[i−1][j−1]∗p[i] 解释 : 前 i i i个烟花,有 j j j个被点燃,可以从前面 f [ i − 1 ] [ j ] ∗ ( 1 − p [ i ] ) f[i-1][j]*(1-p[i]) f[i−1][j]∗(1−p[i]) 不包括自己,所以乘 1 − p [ i ] 1-p[i] 1−p[i]

否则从 f [ i − 1 ] [ j − 1 ] ∗ p [ i ] f[i-1][j-1]*p[i] f[i−1][j−1]∗p[i]也就是当前的被点燃

因为数据范围有点大 [ 1 e 5 ] [ 2 e 1 0 2 ] [1e5][2e10^2] [1e5][2e102]因此考虑使用滚动数组优化

因为总是从前一个转移过来,所以我们令 f [ 2 ] [ N ] f[2][N] f[2][N]

状态转移改变为 : f [ i % 2 ] [ j ] = f [ ( i − 1 ) % 2 ] [ j ] ∗ ( 1 − p [ i ] ) + f [ ( i − 1 ) % 2 ] [ j − 1 ] ∗ p [ i ] f[i\%2][j]=f[(i-1)\%2][j]*(1-p[i])+f[(i-1)\%2][j-1]*p[i] f[i%2][j]=f[(i−1)%2][j]∗(1−p[i])+f[(i−1)%2][j−1]∗p[i]

当然我们需要特判 f [ i ] [ 0 ] f[i][0] f[i][0]

初始化 f [ 0 ] [ 0 ] = 1 f[0][0] = 1 f[0][0]=1

Mycode

const int N = 1e5+10;
double p[N],f[2][N];
int n,k;

void solve(){
	double res = 0 ;
	cin>>n>>k;
	for(int i=1;i>p[i],res+=p[i];
	
	printf("%.4lf\n", res);
	
	f[0][0] = 1;
	
	
	
	for(int i=1;i