BZOJ4318: OSU! (概率DP)

题意:一个串给出每个字符为1的可能性否则为0

　　一段连续的1能获得长度的立方的收益

　　问总收益的期望

题解:设x_i为到第i位时连续的1的期望长度

　　由i-1递推来的贡献如果这一位是0没有贡献如果是1 就是（x_i - 1 + 1）* pi

　　设x2_i为期望长度的平方有(x + 1)^2 可以递推出来 x2_i = x2_i - 1 + 2 * x_i - 1 + 1

　　 ans_i即为期望的得分对于第i位为0贡献就只有ans_i - 1

　　如果为1 就应该减去ans_i - 1以1结尾的贡献再加上连续到i为1结尾的贡献化简一下

#include <bits/stdc++.h>

using namespace std;

double p[];

double x[], x2[], ans[];

int main()

{

    int n;

    scanf("%d", &n);    

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

    {

        scanf("%lf", &p[i]);

        x[i] = p[i] * (x[i - ] + 1.0);

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

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

    }

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

    return ;

}

巴特西

BZOJ4318: OSU! (概率DP)

最新文章

热门文章