bzoj3450期望分数

 

自己只能想到O(n^2)的:

dp[i][j] 表示 以i结尾,长度为j的o串的概率,然后在每次遇到x的时候算分数.

 

正解是:

dp[i]表示前i个的答案,d[i]表示以i结尾的期望长度.

推的时候它用d[i]*d[i]-d[i-1]*d[i-1]来算新增的贡献,有点不明白为什么可以这样(平方的期望应该不等于期望的平方才对吧).

哪天问问jason_yu.

---

这道题,假如我们已经确定了问号的内容,那么我们怎么求该种情况的分数的?

它等于:ans &＃61; sigma d[i]*d[i]-d[i-1]*d[i-1] ( if d[i]&＃61;d[i-1]&＃43;1 ) &＃61; sigma 2*d[i-1]&＃43;1 ( d[i&＃43;1]&＃61;d[i]&＃43;1 )

其中d[i]表示以i结尾的最长的o的长度,

所以本题答案就是 E( sigma d[i]*d[i]-d[i-1]*d[i-1] (d[i]&＃61;d[i-1]&＃43;1) ) &＃61; E( sigma 2*d[i-1]&＃43;1 (d[i]&＃61;d[i-1]&＃43;1) )

而上面那个d[i]&＃61;d[i-1]&＃43;1的等价条件是第i格不是x,这个可以在转移时候判断,于是答案变成了一些2*d[i-1]&＃43;1的期望的和.