题解
$dp[i][j]$表示有$i$个$a$,j个ab时的期望，可得转移方程
$$
dp[i][j]={dp[i+1][j]\times pa +\\
dp[i][j+i]\times pb}
$$
(注意这里需要求的是期望，当前状态的期望由它可能到达的状态求得，而不是能到达它的状态求得)
当$i+j>=k$时，只要末尾中再出现一个$b$，此时的ab子序列个数就变成了$i+j$个，而$i+j>=k$，满足了题目条件。当末尾得到一个$a$时，继续添加，当得到一个$b$时，添加的过程停止。因此当停止时添加的字符个数（包括最后一个$b$）的期望为$1\over pb$（每次有pb的概率停止，那么使过程停止的期望次数是$1\over pb$。类似一个人投篮，每次有$p={2\over 3}$的概率投中，那他投中一次的所需要的投篮次数的期望为${1\over p}=1.5$次），$1\over pb$个字符中，1个b，${1\over pb}-1$个a，则等于增加了${1\over pb}-1={ {1-pb}\over pb}={pa\over pb}$个$ab$子序列
因此可以得出总的方程
$$
\begin{cases}
dp[i][j]={dp[i+1][j]\times pa +\\ dp[i][j+i]\times pb} & i+j<k \\
dp[i][j]=i+j+{pa\over pb} & i+j\ge k
\end{cases}
$$
代码
1 |
|