期望

· · 个人记录

  1. P1365

    设 dp[i] 表示第 i 位的期望，len 为最长的长度

    当是 s[i] 为 o 时

    dp[i]=dp[i-1]+[(len+1)^2-len^2] = dp[i-1]+len*2+1 len=len+1

    当是 s[i] 是 x 时

    dp[i]=dp[i-1] len=0

    当是 ? 时

    dp[i]=dp[i-1]+\frac {[(len+1)^2-len^2]+1+0}{2} len=\frac {len+1}{2}

这个 len 本质上就是最长长度的期望

同理CF235B

P1654

这道题有些变化，维护变成了三次方，一样考虑加上新增的贡献

dp[i]=dp[i-1]+[(len+1)^3-len^3] =dp[i-1]+len^2*3+len*3+1

注意这里的 len 是长度的期望，所以不能直接用一次项的的平方来计算，而是要用上面的展开来计算