luoguP3239 [HNOI2015]亚瑟王 概率期望DP

当初怎么想的来着.....又忘了......

首先，总期望 = 每张卡片的期望之和

求期望，只要我们求出每张卡片被用掉的概率即可

如果直接上状态$f[i][j]$表示在第$i$轮中，第$j$张牌发动的概率

可以发现转移很困难......然而作死的我还是写了一个，$f[i][j] = prod_{k = 1}^{j - 1} (1 - f[i][k])(1 - sumlimits_{k = 1}^{i - 1} f[k][j])p[j]$

嗯.........复杂度$O(Tnr)$看起来很靠谱，然而由于存在大量前置状态的干扰，完全无法确定是不是正确的.......

所以还是换一种思路吧..............

可以发现，考虑一局游戏中一张牌发动的概率

那么，如果考虑每一局它发动的概率，那么这是一个“或”概率，肯定不好求

因此，我们考虑反面，每一局它都不发动的概率，求“与”概率

那么，对于牌$i$而言，它一局不发动的概率跟（有多少轮它可以选择发动与否）有关

也就是说，第$i$张牌不发动的概率跟前面有多少张牌发动了有关

因此，自然地设出状态$f[i][j]$表示前$i$张牌中，还有$j$张牌没有被打出的概率

转移很简单，考虑第$i $张牌有没有被发动

$f[i][j] += f[i - 1][j] *(1 - p[i])^j$（不发动）

$f[i][j] += f[i - 1][j + 1] * (1 - (1 - p[i])^{j + 1})$（发动）

最后求$i$的期望的时候，把所有的$f[i][j]$加权之后统计即可

即$E[i] = sumlimits_{j = 1}^{r} f[i][j] * (1 - (1 - p[i]) ^ j) * v[i]$

注意预处理一下幂即可

复杂度$O(Tnr)$

#include <cstdio>
#include <cstring>
#define dl double
#define ri register int
#define sid 505
using namespace std;

char c;
int n, m, T, d[sid];
dl ans;
dl p[sid], dp[sid][sid];

#define getchar() *S ++
char RR[19191919], *S = RR;
inline int read() {
    int p = 0; c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') { p = p * 10 + c - '0'; c = getchar(); }
    return p;
}

inline dl dread() {
    int p1 = read(); if(c != '.') return (dl)p1;
    dl p2 = 0, p3 = 0.1; c = getchar();
    while(c >= '0' && c <= '9')
    p2 += (c - '0') * p3, p3 *= 0.1, c = getchar();
    return p2 + (dl)p1;
}

int main() {
    fread(RR, 1, sizeof(RR), stdin);
    T = read();
    for(ri t = 1; t <= T; t ++) {
        n = read(); m = read();
        for(ri i = 1; i <= n; i ++)
        p[i] = dread(), d[i] = read(), p[i] = 1.0 - p[i];
        ans = 0.0; p[0] = 1.0;
        dp[0][m] = 1.0;
        for(ri i = 1; i <= n; i ++) {
            dp[i][m + 1] = 0;
            dl pi = p[i - 1], pp = p[i - 1];
            dl np = p[i], tp = p[i];
            for(ri j = 1; j <= m; j ++) {
                dp[i][j] = dp[i - 1][j] * pp; pp *= pi;
                dp[i][j] += dp[i - 1][j + 1] * (1.0 - pp);
                ans += dp[i][j] * (1.0 - tp) * (dl)d[i];
                tp *= np;
            }
        }
        dp[0][m] = 0.0;
        printf("%.10lf
", ans);
    }
    return 0;
}