B. Sample Game题意：有一个随机数生成器，每个数生成的概率为$p_i$，不断生成直到最后一个数小于先前的任意一个数时停止，共生成x个数，问$x^2$的期望 首先可以把$x^2$分解为$1+3+\cdots+(2x+1)$，即从每一步的增量考虑转移方法，若当前长度为x，则增量为2x+1，考虑增量的期望$E(2x+1)=2E(x)+1$，于是只要借助$E(x)$就能进行转移了 因此可以先处理出$f[i]$表示第一个数为$i$时的期望长度$E(x)$，$f[i]=(\sum\limits_{j=i+1}^nf[j]p_j+p_if[i]+\sum\limits_{j=1}^{i-1}p_j)+1$ 再通过$f[i]$计算$f2[i]$，表示第一个数为$i$时长度平方的期望$E(x^2)$，$f2[i]=\sum\limits_{j=i+1}^n p_j(f2[j]+2f[j]+1)+p_i(f2[i]+2f[i]+1)+4\sum\limits_{j=1}^{i-1}p_j$ 答案为$ans=\sum\limits_{i=1}^nf2[i]p_i$     阅读全文