[概率dp] 流浪地球

现在告诉你每只救援队的目标发动机的编号以及这只救援队在规定时间内成功救援的概率，假如有至少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位小数）

本来以为是数学题

没想到是dp题 所以一直在错的方向瞎搞

对每个发动机建边 易求得当前发动机被救活的概率为1 - 所有救援队都没救的概率

题意求的是 只要有任意k个以上发动机被救活的概率和

dp[i][j]表示前 i 台发动机 救援了 j 台的概率
其概率为前 i - 1 台中救援了 j - 1 台然后又救援了第 j 台,和前 i - 1 台中救援了j台，这台没有救援的概率和

ld xp = dp[i - 1][j] * (1 - p[i]) + dp[i - 1][j - 1] * p[i];

完整代码

/*
    Zeolim - An AC a day keeps the bug away
*/

//#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <sstream>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef double ld;
const int INF = 0x3f3f3f3f;
const ld PI = acos(-1.0);
const ld E = exp(1.0);

const int MAXN = 2e3 + 10;

std::vector<ld> arr[MAXN];

ld dp[MAXN][MAXN], p[MAXN];
// dp[i][j]表示前 i台发动机被救援 j 台的概率
//其概率为前 i-1 台中救援了 j-1 台然后 救援了第 j 台 ,前 i-1 台中救援了j台，这台没有救援

int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);     cout.tie(0);
    //freopen("D://test.in", "r", stdin);
    //freopen("D://test.out", "w", stdout);

    int n, m, k, x;
    ld y;

    cin >> n >> m >> k;

    for(int i = 0; i < n; ++i)
    {
        cin >> x >> y;
        arr[x].push_back(y);
    }
    
    for(int i = 1; i <= m; ++i)
    {
        ld rx = ld(1), rs = ld(1);
        for(int j = 0; j < arr[i].size(); ++j)
            rs *= (ld(1) - arr[i][j]);
        p[i] = rx - rs; //每台被救援成功的概率
    }
    dp[0][0] = 1.0;
    for(int i = 1; i <= m; ++i)
    {
        dp[i][0] = dp[i - 1][0] * (1 - p[i]); //一台也没救成的概率
        for(int j = 1; j <= i; ++j)
        {
            ld xp = dp[i - 1][j] * (1 - p[i]) + dp[i - 1][j - 1] * p[i];
            dp[i][j] = xp;
        }
    }

    ld ans = 0;

    for(int i = k; i <= m; ++i)
        ans += dp[m][i];

    cout << fixed << setprecision(3) << ans << '
';

    return 0;
}