解法

一道概率期望类 DP。

我们设状态不考虑当前轮数：这样太难设计了，我太菜不会。考虑设计全局的状态：\(f[i][j]\)意义为考虑前\(i\)张卡牌，且游戏结束时只发动了\(j\)张纸牌的概率。那么答案就是：

\[ ans = \sum_{i = 1}^n d_i \sum_{j = 0}^r dp[i-1][j] * [1 – (1 – p_i)^{r – j}] \]

分析这个式子：期望可以考虑线性叠加每一个点的贡献，威力乘上成功发动的概率；成功的概率可以分成\(j\)张牌成功发动的成功概率，计算连续失败的概率之后补集转换即可。

现在来考虑\(dp\)的求法。首先注意到这些纸牌都排好顺序了：

\[ dp[i][j] = dp[i-1][j] * (1-p_i)^{r – j} + dp[i-1][j-1] * (1 – (1 – p_i)^{r – (j – 1)}) \]

解读一下这个式子：

• 从\(dp[i-1][j]\)进行转移：这个纸牌没有发动，当且仅当剩余的\(r-j\)轮里没有发动，所以写上补集概率的乘方。
• 从\(dp[i-1][j-1]\)进行转移：这张纸牌发动（按顺序），当且仅当它在剩下的\(r-(j-1)\)轮中有发动的可能，所以还是补集转换。

代码

// P3239.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300;
int T, n, r, di[MAX_N];
double pi[MAX_N], dp[MAX_N][MAX_N], f[MAX_N];

double quick_power(double bas, int tim)
{
    double ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas;
        bas = bas * bas;
        tim >>= 1;
    }
    return ans;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        memset(dp, 0, sizeof(dp)), memset(f, 0, sizeof(f));
        scanf("%d%d", &n, &r);
        for (int i = 1; i <= n; i++)
            scanf("%lf%d", &pi[i], &di[i]);
        dp[1][0] = quick_power(1 - pi[1], r);
        dp[1][1] = f[1] = 1 - dp[1][0];
        for (int i = 2; i <= n; i++)
        {
            f[i] = 0;
            for (int j = 0; j <= r; j++)
            {
                dp[i][j] = dp[i - 1][j] * quick_power(1 - pi[i], r - j);
                if (j > 0)
                    dp[i][j] += dp[i - 1][j - 1] * (1 - quick_power(1 - pi[i], r - j + 1));
                f[i] += dp[i - 1][j] * (1 - quick_power(1 - pi[i], r - j));
            }
        }
        double ans = 0;
        for (int i = 1; i <= n; i++)
            ans += f[i] * di[i];
        printf("%.10lf\n", ans);
    }
    return 0;
}