题意
略（看了20min才看懂。。。）
题解
我一开始天真地一轮轮推期望，发现根本不好算。。。
唉~ 不会做就只能抄题解咯 看了一波DOFY大佬的解法qwq
发现有句神奇的话
记住，期望要倒着推。。。
这个是 __debug 曾说的一句话
概率要顺着推，期望要倒着推。
似乎看上去很有道理 运用到这道题上就很优秀了。
我们考虑 \(dp_{i,j}\) 为考虑到 \(i\) 张卡牌（其中 \(i+1 \thicksim n\)，已经考虑完了）并且玩完 \(j\) 轮的期望伤害。
然后有个显然 奇妙的dp方程咯（很神）
\[dp_{i,j}=dp_{i+1,j} \times (1-p_i)^j+(dp_{i+1,j-1}+d_i)*(1-(1-p_i)^j)
\]
\]
考虑分两种
- 对于卡牌 \(i\) ，到 \(j\) 次还没有发动的概率为 \((1-p_i)^j\) 。那么我们可以直接可以乘上后一个的也在第 \(j\) 轮的期望就行了。
- 第 \(j\) 次发动的概率就为 \(1-(1-p_i)^j\) 。那么后一个就在前一轮（\(j-1\) 轮）了，也乘上那个期望。
不难发现，逆推 \(i\) 的话，该算的概率全都会算上，而且不会算错。（因为前面会乘上那个概率来修改后面计算的贡献）
最后答案就是 \(dp_{1,r}\) 了。
这样比网上很多递推然后用概率乘系数的要优秀许多了qwq
时间复杂度 \(\Theta(Tnr)\)
代码
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int N = 1010;
double p[N], d[N], dp[N][N];
int n, r, cases;
int main () {
scanf("%d", &cases);
while (cases --) {
scanf ("%d%d", &n, &r);
For (i, 1, n)
scanf("%lf%lf", &p[i], &d[i]);
Fordown (i, n, 1) {
double P = 1.00 - p[i];
For (j, 1, r) {
dp[i][j] = dp[i + 1][j] * P + (dp[i + 1][j - 1] + d[i]) * (1 - P);
P *= (1.00 - p[i]);
}
}
printf ("%.10lf\n", dp[1][r]);
}
return 0;
}