【BZOJ4318】OSU! 题解（期望）

题目链接

题目大意：给定$n$个操作的成功率$p[i]$。连续成功操作$m$次可以贡献$m^3$的分数。问期望分数。

对于$(x+1)^3$

$=x^3+3x^2+3x+1$

每多连续成功一次，对答案的贡献增加$3x^2+3x+1$。

我们维护这个增加值的期望。

维护$x1$表示$x$的期望，$x2$表示$x^2$的期望。

$x1[i]=(x1[i-1]+1)*p[i]$

$x2[i]=(x2[i-1]+2*x1[i-1]+1)*p[i]$

$ans[i]=ans[i-1]+(3*x2[i-1]+3*x1[i-1]+1)*p[i]$

最后的答案就是$ans[n]$。

双倍经验题：CF235B 比这个题还水。

代码：

#include<bits/stdc++.h>

using namespace std;

double x1[],x2[],ans[],p[];

long long n;

int main()

{

    cin>>n;

    for (int i=;i<=n;i++) cin>>p[i];

    for (int i=;i<=n;i++)

    {

        x1[i]=(x1[i-]+)*p[i];

        x2[i]=(x2[i-]+*x1[i-]+)*p[i];

        ans[i]=ans[i-]+(*x2[i-]+*x1[i-]+)*p[i];

    }

    printf("%.1lf",ans[n]);

    return ;

}

巴特西

【BZOJ4318】OSU! 题解（期望）

最新文章

热门文章