\(\text{Solution:}\)
题目要我们求所有的卡牌期望伤害之和，即 \(\sum_\limits{i=1}^nE(第 i 张牌的伤害)\) ,
\[ \begin{aligned} &\sum_\limits{i = 1}^nE(第i张牌的伤害)\\ =&\sum_\limits{i = 1}^nP(第i张牌使用的概率)×d(i) \end{aligned} \]
所以要求 \(P(第i张牌使用的概率)\) 。
\(p(i)\) 为第i张牌发动技能的概率，
发现 \(P(1) = 1 - (1 - p(1))^r\) , 但是由于每张牌使用一次就结束该轮，我们不是很好地能求出其它的概率，于是考虑递推概率。
设 \(f[i, j]\) 表示前 \(i\) 张牌已经出了 \(j\) 张牌的概率，
- \(f[i, j] \times (1 - p[i + 1])^{r - j} \ \rightarrow\ f[i + 1, j]\) (第 \(i+1\) 张牌不发动技能)
- \(f[i, j] \times (1 - (1 - p[i + 1])^{r - j})\ \rightarrow\ f[i + 1, j + 1]\) (第 \(i+1\) 张牌发动技能)
\[ P(i)=\sum_{j=0}^rf[i - 1, j]\times (1 - (1 - p[i])^{r - j}) \]
然后就做完了。
由于每张牌使用一次就结束该轮，使得我们不是很好地从回合数的角度设状态，而要从牌的角度上设，又因为 “如果这张卡牌不是最后一张，则跳过之(考虑下一张卡牌)" ，所以要有一维 ”当 前用了多少牌" 这一状态。
#include#include #include #include #include #include #include using namespace std;#define LL long long#define debug(...) fprintf(stderr, __VA_ARGS__)#define GO debug("GO\n")inline int rint() { register int x = 0, f = 1; register char c; while (!isdigit(c = getchar())) if (c == '-') f = -1; while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar())); return x * f;}template inline void chkmin(T &a, T b) { a > b ? a = b : 0; }template inline void chkmax(T &a, T b) { a < b ? a = b : 0; }const int N = 300;//fp[i]即为P(i)double fp[N], f[N][N], ans, p[N], d[N], powp[N][N];int n, r;void Init() { for (int i = 1; i <= n; ++ i) { powp[i][0] = 1; for (int j = 1; j <= r; ++ j) powp[i][j] = powp[i][j - 1] * (1 - p[i]); }}int main() {#ifndef ONLINE_JUDGE freopen("xhc.in", "r", stdin); freopen("xhc.out", "w", stdout);#endif int T; scanf("%d", &T); while (T --) { scanf("%d%d", &n, &r); for (int i = 1; i <= n; ++ i) scanf("%lf%lf", p + i, d + i); Init(); memset(fp, 0, sizeof (fp)); memset(f, 0, sizeof (f)); f[1][0] = powp[1][r]; f[1][1] = fp[1] = 1 - f[1][0]; for (int i = 1; i <= n; ++ i) { for (int j = 0; j <= r; ++ j) { fp[i] += f[i - 1][j] * (1 - powp[i][r - j]); f[i][j] += f[i - 1][j] * powp[i][r - j]; if (j) f[i][j] += f[i - 1][j - 1] * (1 - powp[i][r - j + 1]); } } double ans = 0; for (int i = 1; i <= n; ++ i) ans += fp[i] * d[i]; printf("%.10lf\n", ans); }}