西北大学集训队选拔赛（重现赛）- B 饱和式救援

题目

空间限制： 65536K
题目描述


在《流浪地球》电影中，地球上大部分的行星发动机被摧毁。

人类再一次展开全球性救援，现在告诉你每只救援队的目标发动机的编号以及这只救援队在成功救援的概率，假如有至少k个行星发动机能够得到重启，则认为地球会被拯救。

l  输入描述

第一行给出N，M，K。N代表人类派出的救援队总数，M代表被摧毁的行星发动机，K代表至少需要重启的行星发动机总数。(1<=N<=1e5,K<=M<=2000)
接下来N行，每行给出ai,pi，分别代表第i支救援队的目标发动机的编号是ai，救援成功的概率为pi。(1<=ai<=M,0<=pi<=1)
只要有一只救援队顺利抵达该行星发动机，则认为该发动机被成功重启。

l  输出描述

输出地球被救援成功的概率（请严格保留3位小数）

l分析

称发动机被成功重启为“发动机成功”，否则为“发动机失败”。

P（地球被救援成功）=P（至少k台发动机成功）=i=kmP（有i台成功）

动态规划

设dp[i][j]为P（在i台中有j台成功），则

dp[i][j]=dp[i-1][j]*P（发动机i失败）+dp[i-1][j-1]* P（发动机i成功），

用自然语言描述就是

在i台中有j台成功的概率=在i-1台中有j台成功且i失败的概率+ 在i-1台中有j-1台成功且i成功的概率

dp[i][j]的值仅依赖于dp[i-1][j]和dp[i-1][j-1]，因此以递增i的方式计算。

空间复杂度优化：

压缩至一维，则dp[i][j]=dp[i][j]*P（发动机i失败）+dp[i][j-1]* P（发动机i成功），此时需要以递减j的方式计算。

代码 

#include<stdio.h>
int main()
{
	int n,m,k;//n代表救援队总数，m代表故障发动机总数，k代表最少需要重启的发动机数量
	double s[2005]={0};//s[i]存储i号发动机成功概率
	double ss[2005]={0};
    scanf("%d%d%d",&n,&m,&k);
    for(i=0;i<=m;i++) f[i] = 1.0;
    int a;double p;
    while(n--)
		{scanf("%d%lf",&a,&p);//a代表当前发动机编号,p代表当前成功概率
		p[a]=p[a]*(1.0-p);}//更新失败概率
    for (i=1;i<=m;i++) s[i]=1.0-f[i];//计算成功概率
    ss[0] = 1;
    for(int i = 1; i <= m ;++i)//i从1到m递增 
    {
        for(int j = i; j >= 1; --j)//j从i到1递减 
            ss[j] = ss[j]*f[i]+ss[j-1]*s[i];
        ss[0] = ss[0]*f[i];
    }
    double es = 0;//es代表至少有K台成功的概率 
    for(int i = k; i <= m; ++i)
        es += ss[i];//ss[i]代表在m台中有i台成功的概率 
    printf("%.3f\n",es);
    return 0;
}

归纳

dp[i][j]=P（i个独立事件中发生j个）=dp[i-1][j]*P（事件i不发生）+dp[i-1][j-1]* P（事件i发生）