【luoguP3239】[HNOI2015]亚瑟王

严重自闭ing
这个题首先一个直接想法是设dp_{i,j}表示目前考虑到第i个人,恰好在第j轮发动技能的概率……然后就发现这样没法转移了,因为一堆概率都是互相关联的,存在后效性。
考虑一个莫得后效性的状态,设dp_{i,j}表示考虑了前i个人,有j个发动技能的代价,那么dp_{i,j}只会和dp_{i-1,j-1},dp_{i-1,j}有关系,这个人单算不发动技能的概率是(1-p_i)^{r-j},相反的,发动技能的概率就是1-(1-p_i)^{r-j}
因此状态转移式子为

dp_{i,j} = dp_{i – 1, j} \cdot (1-p_i)^{r-j} + dp_{i – 1, j – 1} \cdot (1-(1-p_i)^{r-j})

那么对于每个人来说,发动技能的概率就是

P_i = \sum_{j = 0}^{i – 1}dp_{i-1, j} \cdot (1 – (1 – p_i)^{r – j})

最后答案就是

ans = \sum_{i = 1}^n P_i \cdot d_i

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = - x;
}

int T, n, r, d[225];

double dp[225][140], p[225], P[225][225];

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n >> r;
        for(ri i = 1; i <= n; i ++)
            cin >> p[i] >> d[i];
        memset(dp, 0, sizeof(dp)), memset(P, 0, sizeof(P));
        for(ri i = 1; i <= n; i ++)
        {
            P[i][0] = 1;
            for(ri j = 1; j <= r; j ++)
                P[i][j] = P[i][j - 1] * (1 - p[i]);
        }
        dp[0][0] = 1;
        for(ri i = 1; i <= n; i ++)
            for(ri j = 0; j <= min(i, r); j ++)
            {
                dp[i][j] = dp[i - 1][j] * P[i][r - j];
                if(j > 0)
                    dp[i][j] += dp[i - 1][j - 1] * (1 - P[i][r - j + 1]);
            }
        double pri = 0.0;
        for(ri i = 1; i <= n; i ++)
        {
            double tmp = 0.0;
            for(ri j = 0; j < min(i, r); j ++)
                tmp += dp[i - 1][j] * (1 - P[i][r - j]);
            pri += tmp * d[i];
        }
        printf("%.10lf\n", (double)pri);
        //cout << pri << '\n';
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注