P1654 OSU!——期望的线性性质与转化

li_cat · 2025-06-07 11:50:23 · 个人记录

初见

初见的话发现很难处理，因为期望的立方不符合期望的线性性质

• 线性性质即对加法和标量乘法保持

于是可以试着转化

一次

考虑长度贡献为1次方的情况

设X1_i为到第i个位置时的期望分数

不难看出:

可能性有两种，一种为1，接上了之前的期望长度，一种为0一无所有

二次

考虑长度贡献为2次方

设X2_i为到第i个位置时的期望分数

可能性有两种：

• 成功为1，接上了前面的期望长度
  考虑前面的期望长度为x的情况
  • 此时增加的量为(x+1)^2-x^2=2x+1
• 失败为0，一无所有

也就是说

（注意，此时我们并没有将期望本身作乘方，因为期望是不支持这样做的）

三次

回到了题目，考虑长度贡献为3次方

这次dp_i为到第i个位置时的总计期望分数

同上，考虑前面长度为x时，接上增加的量为(x+1)^3-x^3=3\times x^2+3\times x+1

即

于是就能过了

AC Code:

#include <bits/stdc++.h>
#define db double
using namespace std;

const int MAXN=1e5+5;

int n;
db X1[MAXN],X2[MAXN],dp[MAXN],p[MAXN];

void work(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lf",&p[i]);
    X1[0]=X2[0]=dp[0]=0;
    for(int i=1;i<=n;++i){
        X1[i]=(X1[i-1]+1)*p[i];
        X2[i]=(X2[i-1]+2*X1[i-1]+1)*p[i];
        dp[i]=dp[i-1]+(X2[i-1]*3+X1[i-1]*3+1)*p[i];
    }
    printf("%.01lf",dp[n]);
}//

int main(){
    work();
    return 0;
}