HNOI2015 亚瑟王

题目大意

给你 张牌，顺序进行 轮游戏， 每张牌都有一个触发技能概率，技能都有一个伤害，如果一张牌触发过 以后他都会被跳过，一张牌触发之后这轮结束

题解

因为每一张牌的贡献都是1， 所以我们只需要考虑概率就行。

对于第一张牌， 正难则反，他在 轮中 触发的概率为

%5Er%0A#card=math&code=%5Clarge%201-%281-p%5B1%5D%29%5Er%0A&id=fhS9L)

考虑 第二张牌 如果第一张牌触发过了 那么有一轮 根本就轮不到他了

%5E%7Br-1%7D%0A#card=math&code=%5Clarge%201-%281-p%5B2%5D%29%5E%7Br-1%7D%0A&id=z1TGI)

所以我们考虑用 表示在全部的回合中 前 张牌 触发了 张的概率

考虑转移 当第 张牌发动 因为有 轮都直接跳过了

)*f%5Bi-1%5D%5Bj-1%5D%0A#card=math&code=%5Clarge%20f%5Bi%5D%5Bj%5D%2B%3D%281-%281-p%5Bi%5D%5E%7Br-j%2B1%7D%29%29%2Af%5Bi-1%5D%5Bj-1%5D%0A&id=o1v6H)

考虑他不发动的情况

*f%5Bi-1%5D%5Bj%5D%0A#card=math&code=%5Clarge%20f%5Bi%5D%5Bj%5D%2B%3D%281-p%5Bi%5D%5E%7Br-j%7D%29%2Af%5Bi-1%5D%5Bj%5D%0A&id=apSZN)

转移的时候 每个底层 加两次

最后收集答案

%7Df%5Bi-1%5D%5Bj%5D*(1-(1-p%5Bi%5D%5E%7Br-j%7D))%0A#card=math&code=%5Clarge%20g%5Bi%5D%3D%5CSigma_0%5E%7Bmin%28r%2Ci-1%29%7Df%5Bi-1%5D%5Bj%5D%2A%281-%281-p%5Bi%5D%5E%7Br-j%7D%29%29%0A&id=FbceP)

#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;
}