首先我们考虑k=1的情况，当k=1时，我们直接枚举这天遇到了哪一件事，并输出结果即可。

然后我们考虑k≤5的情况，我们可以暴力枚举每一天遇到了什么事并一次计算，复杂度O(5^5)。

遇到此类期望计数问题，我们可以使用DP来解决。

考虑DP[i][j][k]，意思表示食物数为i，金币数为j，第k天的概率。

我们可以根据五种事情推得状态转移方程。

DP[i][j][k]=(DP[i+1][j][k-1]+DP[i-1][j+1][k-1]+DP[i][j+2][k-1]+DP[i][j+3][k-1]+DP[i][j][k])×0.2

然后，我们发现DP[][][k]依赖且仅依赖于DP[][][k-1]，我们可以滚掉第三维。

最终时间复杂度O(nmk)，空间复杂度O(nm)。

Tags:dp,math,probabilities Difficulty:1600