topcoder DoubleLive

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

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

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

考虑最后答案求的是啥:

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

于是我们其实只需要对所有 $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]$

文章作者: yijan
文章链接: https://yijan.co/2021/02/13/topcoder-doublelive/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog