正文
【洛谷1654/BZOJ4318】OSU！（期望DP）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目：
洛谷1654
分析：
本人数学菜得要命，这题看了一整天才看明白……
先说说什么是“期望”。不太严谨地说，若离散型随机变量（可以看作“事件”）\(X\)取值为\(x_i\)的概率为\(p_i\)，则它的期望\(E(X)\)为：
\[E(X)=\sum_i x_ip_i
\]
\]
（下面大段胡扯可以跳过）
举个例子：Monster of the Mouth设计了一款游戏，从某知名OIer兔崽子2018年9月21日-22日在BZOJ上的提交记录中随机抽一个，如果是AC则Inspector_Javert请兔崽子吃九根烤肠，否则兔崽子请Inspector_Javert吃三根烤肠，Inspector_Javert期望吃到多少根烤肠？
首先我们看一眼兔崽子的提交记录，发现他在这两天内提交了\(12\)次，其中\(2\)次AC，\(4\)次CE，\(3\)次MLE，\(1\)次TLE，\(1\)次WA，\(1\)次RE （印证了那句名言：AC率这么低/CE率这么高一定是用提交框写代码的兔崽子）
那么Inspector_Javert损失九根烤肠的概率\(P(-9)=\frac{2}{12}=\frac{1}{6}\)
Inspector_Javert得到三根烤肠的概率\(P(3)=\frac{4+3+1+1+1}{12}=\frac{5}{6}\)
则期望\(E(X)=-9*\frac{1}{6}+3*\frac{5}{6}=1\)
所以Inspector_Javert期望吃到\(1\)根烤肠
说成人话，平均每玩一次Inspector_Javert就能得到一根烤肠。如果Inspector_Javert和兔崽子玩了\(n\)次，当\(n\)趋于正无穷时，Inspector_Javert比兔崽子多吃到烤肠的数量趋于\(n\)
（烤肠真香）
期望有一个很重要的性质：线性性。即对于两个随机变量\(X\)和\(Y\)，存在
\[E(X+Y)=E(X)+E(Y)
\]
\]
继续上面的例子：如果Inspector_Javert和另一个知名OIer小恐龙也玩了上面的那个游戏，那么如果\(X\)表示Inspector_Javert多吃的烤肠总数，\(X_1\)表示比兔崽子多吃的烤肠数，\(X_2\)表示比小恐龙多吃的烤肠数，则
\[E(X)=E(X_1)+E(X_2)
\]
\]
人话：比两个OIer多吃的=比兔崽子多吃的+比小恐龙多吃的（这个很显然吧）
(然而小恐龙AC率爆表导致Inspector_Javert期望损失惨重……qwq)
言归正传，来冷静分析这道题的一个弱化版：得分是极长'1'串的长度，而非长度的立方。首先肯定能想到dp，用\(f_i\)表示前\(i\)个位置的期望得分。同时，用\(g_i\)表示以\(i\)结尾的极长'1'串的长度的期望，\(p_{i,j}\)表示以\(i\)结尾的极长'1'串长为\(j\)的概率。输入数据记作\(p'_i\)，\(p'_0=0\)
注意此处以\(i\)结尾的极长'1'串的定义为
满足位置\((j-1)\)的数为\(0\)的全'1'串\([j,i]\)
（即不考虑位置\(i\)后面的情况）
显然有\(p_{i,j}=p_{i-1,j-1}*p'_i\)，\(p_{i,0}=1-p'_i\)
由期望的定义可得
\[g_i=\sum_{k=0}^i p_{i,k}*k=\sum_{k=1}^i p_{i,k}*k
\]
\]
\[g_{i-1}=\sum_{k=0}^{i-1} p_{i-1,k}*k
\]
\]
给下面的式子乘上\(p'_i\)，就得到
\[\begin{aligned}
g_{i-1}*p'i & =\sum_{k=0}^{i-1} p_{i,k+1}*k\\
&=\sum_{k=1}^{i} p_{i,k}*(k-1)\\
&=\sum_{k=1}^{i} p_{i,k}*k-\sum_{k=1}^{i} p_{i,k}\\
\end{aligned}
\]
g_{i-1}*p'i & =\sum_{k=0}^{i-1} p_{i,k+1}*k\\
&=\sum_{k=1}^{i} p_{i,k}*(k-1)\\
&=\sum_{k=1}^{i} p_{i,k}*k-\sum_{k=1}^{i} p_{i,k}\\
\end{aligned}
\]
可以发现第一项就是\(g_i\)，而\(\sum_{k=1}^{i}p_{i,k}\)就等于\(p'_i\)（因为所有\(p_{i,k}\)不重不漏地包含了位置\(i\)为\(1\)的所有情况）。于是我们得到一个递推式：
\[g_i=p'_i*(g_{i-1}+1)
\]
\]
根据期望的线性性，前\(i\)点的期望得分=前\(i-1\)点的期望得分+\(i\)点的期望得分（也就是长度）
所以DP方程就是\(f_i=f_{i-1}+g_i\)？
恭喜你gg了
注意，当\(i\)点为\(1\)时，以\(i-1\)结尾的'1'串不再是“极长”的（这里“极长”是题目中的定义而非上文中的定义），它们不再作出贡献。所以事实上如果\(i\)点为\(1\)，我们有\(p'_i\)的概率获得\(g_{i-1}\)的损失，也就是说期望损失为\(p'_i*g_{i-1}\)
所以DP方程应该是
\[f_i=f_{i-1}+g_i-g_{i-1}*p'_i
\]
\]
现在考虑，如果得分是极长'1'串长度的平方呢？（注意期望的平方不等于平方的期望）我们记以\(i\)结尾的极长'1'串长度的平方为\(g'_i\)，同理可得
\[g'_i=\sum_{k=0}^i p_{i,k}*k^2=\sum_{k=1}^i p_{i,k}*k^2
\]
\]
那么
\[\begin{aligned}
g'_{i-1}*p'_i&=\sum_{k=0}^{i-1}p_{i,k+1}*k^2\\
&=\sum_{k=1}^ip_{i,k}*(k-1)^2\\
&=\sum_{k=1}^ip_{i,k}*(k^2-2k+1)\\
&=g'_i-2g_i+p'_i
\end{aligned}
\]
g'_{i-1}*p'_i&=\sum_{k=0}^{i-1}p_{i,k+1}*k^2\\
&=\sum_{k=1}^ip_{i,k}*(k-1)^2\\
&=\sum_{k=1}^ip_{i,k}*(k^2-2k+1)\\
&=g'_i-2g_i+p'_i
\end{aligned}
\]
得到递推式
\[\begin{aligned}
g'_i&=g'_{i-1}*p'_i+2g_i-p'_i\\
&=g'_{i-1}*p'_i+2(g_{i-1}+1)*p'_i-p'_i\\
&=p'_i*(g'_{i-1}+2g_{i-1}+1)
\end{aligned}
\]
g'_i&=g'_{i-1}*p'_i+2g_i-p'_i\\
&=g'_{i-1}*p'_i+2(g_{i-1}+1)*p'_i-p'_i\\
&=p'_i*(g'_{i-1}+2g_{i-1}+1)
\end{aligned}
\]
那么最终的DP方程就是（和上面的几乎一模一样）
\[f_i=f_{i-1}+g'_i-g'_{i-1}*p'_i
\]
\]
得分是长度三次方的情况（原题）和平方的情况非常相似，读者可以自行脑补。
代码：
说了这么多，代码其实非常短……
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <iomanip>
using namespace std;
namespace zyt
{
const int N = 1e5 + 10;
double f[N], g[N][3];
int work()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
double p;
cin >> p;
g[i][0] = p * (g[i - 1][0] + 1);
g[i][1] = p * (g[i - 1][1] + g[i - 1][0] * 2 + 1);
g[i][2] = p * (g[i - 1][2] + 3 * g[i - 1][1] + 3 * g[i - 1][0] + 1);
f[i] = f[i - 1] + g[i][2] - g[i - 1][2] * p;
}
cout.setf(ios::fixed);
cout << setprecision(1) << f[n];
return 0;
}
}
int main()
{
return zyt::work();
}
