OceanEye's Blog

是时候表演真正的技术了!

@OceanEye2月前

05/4
19:49
OI

BZOJ4318

期望DP
题目要求维护三次方
所以要把二次和一次的期望也给维护了,接着考虑我们DP的含义是什么。
DP[3][i]=DP[3][i-1] + (增长幅度=x^3-(x-1)^3)*(增长概率=p[i])
上面那个三次方展开一下就可以做了

BZOJ4318