lp1654 OSU!

真是棒到不行!OSU!

首先,我们可以知道,对于长度为\(x\)的线段,在其后加上一个新的长度为1的线段,新线段的价值是\((x+1)^3\)
那么,价值的差便是:
$$3*x^2+3*x+1$$
而这样的贡献必须要当前点被选中才可行的。似乎可以得到:
$$f_{i}=f_{i-1}*(1-p_{i})+(f_{i-1}^3+3*f_{i-1}^2+3*f_{i-1}+1)*p_{i}$$
但仔细观察就可以发现这样显然是错误的。
这是因为,平方的期望不等于期望的平方。
因此,对于平方的期望,以及一次方的期望,我们应当另外维护两个函数\(g,u\),分别表示平方的期望和一次方的期望。
那么:
$$g_{i}=(g_{i-1}+2*u_{i-1}+1)*p_{i}$$
$$u_{i}=(u_{i-1}+1)*p_{i}$$
于是:
$$f_{i}=f_{i-1}+(3*g_{i-1}+3*u_{i-1}+1)*p_{i}$$
问题得解。
这一题还是很有思维难度的。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
double p[100005],u[100005],g[100005],f[100005];
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf",&p[i]);
    }
    u[0]=g[0]=f[0]=0;
    double ans=0;
    for(int i=1;i<=n;++i){
        u[i]=(u[i-1]+1)*p[i];
        g[i]=(g[i-1]+2*u[i-1]+1)*p[i];
        f[i]=f[i-1]+(3*g[i-1]+3*u[i-1]+1)*p[i];
        ans+=f[i];
    }
    printf("%.1lf",f[n]);
    
}
int main(){
    init();
    return 0;
}

“lp1654 OSU!”的2个回复

  1. u和g的公式略有差错。
    一次方的期望和二次方的期望的计算公式应该是$latex u_i=(u_{i-1}+1)*p_i $ 和 $latex g_i=(g_{i-1}+2*u_{i-1}+1)*p_i $
    因为,u和g维护的仅仅是从当前往回最大的连续1段的期望而已。你的程序中似乎也是按这个写的。

发表评论

您的电子邮箱地址不会被公开。