期望

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

LOJ-2538 「PKUWC2018」Slay the Spire

f[i][j]f[i][j]表示前ii张用了jj张强化，那么转移为

f[i][j]={f[i−1][j]+f[i−1][j−1]∗a[i]j≤k−1f[i−1][j]+f[i][j]otherwisef[i][j] = \begin{cases} f[i - 1][j] + f[i - 1][j - 1] * a[i] \quad j\leq k-1\\ f[i-1][j]+f[i][j] \quad otherwise \end{cases}

g[i][j]g[i][j]表示前ii张用了jj张攻击，那么转移为

g[i][j]={g[i−1][j]+Ci−1j−1∗b[i]j≤m−(k−1)g[i−1][j−1]+g[i−1][j]+Ci−1j−1∗b[i]otherwiseg[i][j]= \begin{cases} g[i - 1][j]+C_{i-1}^{j-1}*b[i] \quad j\leq m-(k-1)\\ g[i - 1][j - 1] + g[i - 1][j] + C_{i-1}^{j-1}*b[i] \quad otherwise \end{cases}

那么答案为∑i=0mf[i]⋅g[m−i]\sum_{i=0}^{m} f[i]\cdot g[m-i]

LightOJ-1151 Snakes and Ladders

题意: 每次抛骰子走1−61-6步，问走到100100的期望，其中有nn个格子进行传送

思路：如果没有传送则，f[i]=16⋅∑j=16f[i+j]f[i]=\frac{1}{6}\cdot \sum_{j=1}^{6} f[i+j]如果有传送，则f[i]=f[nxt[i]]f[i]=f[nxt[i]]

高斯消元

知识点

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！