题目链接：https://ac.nowcoder.com/acm/contest/892/B
题目大意：


思路：
可以把每个发动机不能重启的概率求出来,每个救援队都不能成功。
用容斥求出成功的概率p[i]。

for(int i=1;i<=m;i++)
    {
        double s=1;
        for(int j=0;j<v[i].size();j++)
        {
            s*=(1-v[i][j]);
        }
        p[i]=1.0-(s);
    }

dp[i][j]表示前i个发动机能重启j个发动机的概率。

memset(dp, 0, sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=m;i++)
{
    for(int j=0;j<=i;j++)
    {
        if(j==0)
        {
            dp[i][j]=dp[i-1][j]*(1-p[i]);
        }
        else
        {
            dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
        }
    }
}

如果求dp[n][j]（k<=j<=n）的和就行了。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

double dp[2005][2005];
double p[2005];
vector<double> v[100005];

int main()
{
    int n, m, k, a;
    double pp;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d%lf",&a,&pp);
        v[a].push_back(pp);
    }
    for(int i=1;i<=m;i++)
    {
        double s=1;
        for(int j=0;j<v[i].size();j++)
        {
            s*=(1-v[i][j]);
        }
        p[i]=1.0-(s);
    }
    memset(dp, 0, sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==0)
            {
                dp[i][j]=dp[i-1][j]*(1-p[i]);
            }
            else
            {
                dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
            }
        }
    }
    double ans=0;
    for(int i=k;i<=m;i++)
    {
        ans+=dp[m][i];
    }
    printf("%.3f\n",ans);

    return 0;
}