是一个概率期望相关的题目, 但并没有使用期望的线性性质或者\(f[S]=\sum (f[T]+v_{S \to T}) \times p_{S \to T}\) 这类常见的dp思路。

这个题目是从期望的定义出发, 也就是求出概率再乘权值得到期望。

题目链接

题目大意

游戏进行\(r\)轮, 有\(n\)张牌, 每轮按照从小到大的顺序判断每张牌,如果这张牌已经出过就跳过,否则有\(p_i\)的概率打出, 并造成\(d_i\)点伤害。

求造成的期望伤害。

解题报告

\(r\)轮游戏? 实际是\(r\)次出牌的机会,打出一张牌会消耗一次机会。

每轮游戏都是从小到大的顺序判断每张牌, 所以如果确定前\((i-1)\)张牌,是否在\(r\)轮中的某一轮打出或者没有打出过, 那么第\(i\)张牌可以看做第\(1\)张牌,不受任何其他牌的影响。

再一点, 就是\(r\)轮游戏实际是没有区别的, 也就是说状态不需要记录具体每一轮游戏是否被\((i-1)\)张牌占用, 只需要记录剩余多少轮游戏就可以。

如果确定前\((i-1)\)个牌占用了若干轮游戏, 记录\(f[i][j]\)表示到第\(i\)张牌, 还剩\(j\)轮游戏没有被占用的概率。 \[ \left \lbrace \begin{aligned} &f[i][j]*(1-p_i)^j \to f[i+1][j]\\ &f[i][j]*(1-(1-p_i)^j) \to f[i+1][j-1] \end{aligned} \right. \] 然后\(\text{Prob(i)}=\sum f[i][j]*(1-(1-p_i)^j)\) . \[ \text{ans} = \sum d_i * \text{Prob}(i) \] 搞定喽。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
typedef double ff;
const int N=233;
ff f[N][N],p[N],g[N];
int n,r,d[N],test;
inline void slv() {
memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
f[0][r]=1.0; rep(i,1,n) {
ff _p=1; rep(j,0,r) {
if (f[i-1][j]) {
f[i][j]+=f[i-1][j]*_p;
if (j) f[i][j-1]+=f[i-1][j]*(-_p+1),g[i]+=f[i-1][j]*(-_p+1);
}
_p*=(-p[i]+1);
}
}
ff as=0;
rep(i,1,n) as+=g[i]*d[i];
printf("%.10lf\n",as);
}
int main() {
scanf("%d",&test); while (test--) {
scanf("%d%d",&n,&r);
rep(i,1,n) scanf("%lf%d",&p[i],&d[i]);
slv();
}
return 0;
}

留言