题解 P3239 【[HNOI2015]亚瑟王】

· · 题解

如果能够求出每张卡牌在所有r轮中被发动的概率g[]，那么答案显然为：

\sum_{i=1}^ng[i]d[i]

第一步推出，g[1]=1-(1-p[1])^r。

再考虑第二张：

情况一：如果第1张牌没有发动过技能，那么第2张牌发动技能的概率为1-(1-p[2])^r。

情况二：如果第1张牌发动过1次技能，那么在第1张牌发动技能的那一轮，第2张牌绝对不会再发动技能了，因此第2张牌发动技能的概率为1-(1-p[2])^{r-1}。

结合这个例子，可以得到，对于任意的i>1，在第1张牌到第i-1张牌在所有r轮内是否发动技能已经确定的情况下，第i张牌被发动技能的概率只取决于第1张牌到第i-1张牌中有多少张发动了技能。即如果有j张发动了技能，那么在此情况下第i张牌发动技能的概率为1-(1-p[i])^{r-j}。

根据这个性质，就能想到一个DP模型：

转移就比较好想了。分第$i$张牌发动与不发动两种情况： 1：发动。那么前$i-1$张牌一定有$j-1$张牌被发动技能，因此对于第$i$张牌，在$r$轮中有$j-1$轮已经不会再发动技能了。所以： $f[i][j]+=(1-(1-p[i])^{r-j+1})f[i-1][j-1]

2：不发动。那么前i-1张牌中一定有j张牌被发动技能，因此对于第i张牌，在r轮中有j轮是绝对不会再发动技能的。所以：

f[i][j]+=(1-p[i])^{r-j}f[i-1][j]

因此，完整的转移方程为：

f[i][j]=((1-(1-p[i])^{r-j+1})f[i-1][j-1])[j>0] +((1-p[i])^{r-j}f[i-1][j])[i\neq j]

那么求g就更容易了：

g[i]=\sum_{j=0}^{\min(i-1,r)}(1-(1-p[i])^{r-j})f[i-1][j]

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 234, R = 143;
int n, r, d[N];
double p[N], f[N][R], g[N], pw[N][R];
void work() {
    memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g));
    int i, j; scanf("%d%d", &n, &r);
    for (i = 1; i <= n; i++) scanf("%lf%d", &p[i], &d[i]), pw[i][0] = 1;
    if (!r) return (void) puts("0.0000000000");
    for (i = 1; i <= n; i++) for (j = 1; j <= r; j++)
        pw[i][j] = pw[i][j - 1] * (1.0 - p[i]);
    f[1][0] = pw[1][r]; f[1][1] = g[1] = 1.0 - pw[1][r];
    for (i = 2; i <= n; i++) for (j = 0; j <= min(i, r); j++) {
        if (j) f[i][j] += f[i - 1][j - 1] * (1.0 - pw[i][r - j + 1]);
        if (i != j) f[i][j] += f[i - 1][j] * pw[i][r - j];
    }
    for (i = 2; i <= n; i++) for (j = 0; j <= min(i - 1, r); j++)
        g[i] += f[i - 1][j] * (1.0 - pw[i][r - j]);
    double ans = 0;
    for (i = 1; i <= n; i++) ans += g[i] * d[i];
    printf("%.10lf\n", ans);
}
int main() {
    int T; cin >> T; while (T--) work();
    return 0;
}