OceanEye's Blog

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

@OceanEye4月前

05/4
19:49
OI

BZOJ4318

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

BZOJ4318

@OceanEye4月前

05/3
18:56
OI

BZOJ1419

期望DP
和班上的一个物理大佬一起搞了二十分钟吧……然后发现这个期望(R,B)只和(R-1,B)以及(R,B-1)相关
然后就一个for循环再用一下滚动数组就可以了
dp[r][b]=(dp[r][b-1]-1)*b/(r+b) + (dp[r-1][b]+1)*r/(r+b)

BZOJ1419