P1654 OSU!

# 期望dp ## 当无法直接硬刚时，请考虑增量 ### 1. 观察 ``` 由立方和公式可得 f[i]=p[i]*(f[i-1]+3*期望长度的平方+3*期望长度+1)+ (1-p[i])*(f[i-1]); ``` ### 2. 维护 考虑先维护到第i个数的期望长度 ``` x[1][i]=p[i]*(x[1][i-1]+1) ``` 不错，再考虑维护到第i个数的期望长度的平方 ``` 由平和公式可得 x[2][i]=p[i]*(x[2][i-1]+2*期望长度+1)+ ``` 很好，这就搞出了f[i] ### 3.撕烤 本题直接维护价值很难维护，因为你并不知道前面有多少个1 但可以转换角度，考虑其增量，从而转换为可以维护的到第i位的期望长度与平方 这种转换的思想是值得借鉴的 至此，斩杀