topcoder DoubleLive

好题。类似 Students Camp 的优化。考虑 $dp[i][j][k]$ 表示当前还剩下 $i$ 个熊两血，$j$ 个一血，其中有 $k$ 个是人。

直接转移复杂度是 $O(1)$ 状态共 $O(n^3)$ 种，复杂度 $O(n^3)$ 。

考虑怎么优化这个 $dp$ 。先把状态转移的式子写出来

$dp[i][j][k] = \frac{i+1}{i+j}dp[i+1][j-1][k]+\frac{j+1-k}{i+j+1}dp[i][j+1][k]+\frac{k+1}{i+j+1}dp[i][j+1][k+1]$

考虑最后答案求的是啥：

$dp[i][j][k]\times k \times (i+j-k) \times (i+j)$

于是我们考虑保留前两维，要求的是

$(i+j)(-\sum_{k} dp[i][j][k] k^2 + (i+j)\sum_{k} dp[i][j][k]k)$

于是我们其实只需要对所有 $dp[i][j][k]$ 乘上 $k,k^2$ 做前缀和即可。

设 $s_1[i][j] = \sum_{t \ge 0} dp[i][j][t]t,s_2[i][j] = \sum_{t \ge 0} dp[i][j][t]t^2$ 。考虑求 $s_1[i][j]$

$s_1[i][j] = \frac{i+1}{i+j} s_1[i+1][j-1] + \frac{j}{i+j+1} s_1[i][j+1]\\ s_2[i][j] = \frac{i+1}{i+j} s_2[i+1][j-1] + \frac{(j-1)s_2[i][j+1] + s_1[i][j+1]}{i+j+1}$