NC25546. 饱和式救援
描述
“在全球性救援开始的0.42秒后，MOSS就已经推算出结果，这是一场注定徒劳的救援。”
在《流浪地球》电影中，虽说在引爆木星之后推动了地球离开木星，但是大爆炸摧毁了地球上大部分的行星发动机。
人类再一次展开全球性救援。此时的MOSS已经被烧毁，现在告诉你每只救援队的目标发动机的编号以及这只救援队在规定时间内成功救援的概率，假如有至少k个行星发动机能够得到重启，则认为地球会被拯救。请你设计一个程序，帮助人类完成这个计算。
输入描述
第一行给出N，M，K。N代表人类派出的救援队总数，M代表被摧毁的行星发动机，K代表至少需要重启的行星发动机总数。(1<=N<=1e5,K<=M<=2000)
接下来N行，每行给出ai,pi，分别代表第i支救援队的目标发动机的编号是ai，救援成功的概率为pi。(1<=ai<=M,0<=pi<=1)
只要有一只救援队顺利抵达该行星发动机，则认为该发动机被成功重启。
输出描述
输出地球被救援成功的概率（请严格保留3位小数）
示例1
输入:
3 2 2 1 1 1 1 2 0.5
输出:
0.500
C++14(g++5.4) 解法, 执行用时: 36ms, 内存消耗: 868K, 提交时间: 2019-05-13 23:34:00
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,m,k,aa;
double pp,p[2100],f[2100],ans;
int main(){
scanf("%d%d%d",&n,&m,&k);
fo(i,1,m) p[i]=1;//1...k!!!!
fo(i,1,n){
scanf("%d%lf",&aa,&pp);
p[aa]*=(1-pp);
}
f[0]=1;
fo(i,1,m){
fd(j,i,1) f[j]=f[j]*p[i]+f[j-1]*(1-p[i]);
f[0]*=p[i];
}
fo(i,k,m) ans+=f[i];
printf("%.3f\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 34ms, 内存消耗: 624K, 提交时间: 2019-05-11 17:31:02
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,m,k,aa;
double pp,p[2100],f[2100],ans;
int main(){
scanf("%d%d%d",&n,&m,&k);
fo(i,1,m) p[i]=1;//1...k!!!!
fo(i,1,n){
scanf("%d%lf",&aa,&pp);
p[aa]*=(1-pp);
}
f[0]=1;
fo(i,1,m){
fd(j,i,1) f[j]=f[j]*p[i]+f[j-1]*(1-p[i]);
f[0]*=p[i];
}
fo(i,k,m) ans+=f[i];
printf("%.3f\n",ans);
return 0;
}