Chlience

【题解】LOJ 2112 「HNOI2015」亚瑟王
ProblemLOJ 2112Thought根据期望的线性性,我们只需要求出每张卡被使用的概率乘上其价值即可显然,...
扫描右侧二维码阅读全文
11
2019/02

【题解】LOJ 2112 「HNOI2015」亚瑟王

Problem

LOJ 2112

Thought

根据期望的线性性,我们只需要求出每张卡被使用的概率乘上其价值即可

显然,第一张卡被抽中的概率 $g[1]=1-(1-p[i])^r$

我们发现,如果一轮中某张卡前面的卡被抽了,这一轮根本就不会轮到它
也就是说,每张卡被抽的概率和前面的卡被抽了多少张有关

设 $f[i][j]$ 为在 $r$ 轮中前 $i$ 张卡出了 $j$ 张的概率
那么显然第 $i$ 张卡会被判断 $r-j$ 次,恰好不被抽中的概率为 $(1-p[i])^{r-j} $ ,所以说其被抽中的概率就是 $1$ 减去每次都不被抽中的概率,即 $g[i]=\sum f[i-1][j]*(1-(1-p[i])^{r-j})$

那么考虑如何求 $f$

显然,一共有两种可能

  1. 第 $i$ 张牌没有被选
  2. 选择了第 $i$ 张牌

通过这两种情况我们可以写出方程

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

最后记得不要在线 $qpow$ 否则可能会炸...

Code

#include <bits/stdc++.h>
using namespace std;
double f[300][300];
double g[300];
double p[300];
double P[300][300];
int d[300];
int n, m;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while ((ch > '9' || ch < '0') && ch != '-') ch = getchar();
    if (ch == '-')
        flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
    return ans * flag;
}
double qpow(double a, int b) {
    double ans = 1;
    while(b) {
        if(b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}
void work() {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    n = read(), m = read();
    for (int i = 1; i <= n; i++) scanf("%lf%d", &p[i], &d[i]);
    f[1][0] = qpow((1.0 - p[1]), m);
    f[1][1] = g[1] = 1.0 - f[1][0];
    for(int i = 1; i <= n; ++ i) {
        P[i][0] = 1;
        for(int j = 1; j <= m; ++ j)
            P[i][j] = P[i][j - 1] * (1.0 - p[i]);
    }
    double ans = g[1] * d[1];
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= min(i, m); j++) {
            if (j <= min(m, i - 1))
                g[i] += f[i - 1][j] * (1.0 - P[i][m - j]);
            if (j != 0)
                f[i][j] += f[i - 1][j - 1] * (1.0 - P[i][m - j + 1]);
            if (i != j)
                f[i][j] += f[i - 1][j] * P[i][m - j];
        }
        ans += g[i] * d[i];
    }
    printf("%.10lf\n", ans);
}
int main() {
    int t = read();
    while (t--) work();
    return 0;
}
Last modification:February 11th, 2019 at 09:16 am

Leave a Comment