291312a_tải nhạc

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

一个序列长度是L，每个位置取1的概率是p，取0的概率是1 – p。连续的n个1的得分是1 + 2 + …… + n。求分数的期望。

http://www.bnuoj.com/bnuoj/problem_show.php?pid=29140

dp[i][j]为长度是i的序列，后j个都是1的概率，f[i]是长度为i的序列的得分。（EX = ∑xi * pi, f[i]就是xi * pi）ans = ∑f[i]

dp[0][0] = 1;                                                    f[0] = 0;

dp[1][0] = 1 – p, dp[1][i] = p;                            f[1] = p;

我们考虑L = 3的情况， 可能的序列为：

000

001

010

011

100

101

110

111

考虑第1为是1，只有后面4个序列的第1位是1对答案的贡献为:p * (1 – p) * (1 – p) * 1 + p * (1 – p) * p * 1 + p * p * (1 – p) * 1 + p * p * p * 1 = p，而f[1]同样为p。

 第2位是1的序列对答案的贡献为:(1 – p) * p * (1 – p) * 1 + (1 – p) * p * p * 1 + p * p * (1 – p) * 2 + p * p * p * 2 = p + p * p。

 第3位是1的序列对答案的贡献为:(1 – p) * (1 – p) * p * 1 + (1 – p) * p * p * 2 + p * (1 – p)  * p * 1 + p * p * p * 3 = p + p * p + p * p * p。对于序列001和101来说，在第3位得分都是1，(1 – p) * (1 – p) * p * 1 + p * (1 – p)  * p * 1 = (1 – p) * p。在不考虑第3位 情况下，00和10构成dp[2][0]，由于它们的第3位都是1，所以其概率为dp[2][0] * p。

由此可以推出dp[2][0] = 1 – p。并且可以依次推出dp[i][0] = 1 – p。

于是就可以这样做~~~

   for(int i=1; i<=L; i++){
            dp[i][0] = 1.0 - p;
            f[i] = 0;
            for(int j=1; j<=i; j++){
                dp[i][j] = dp[i - 1][j - 1] * p;
                f[i] += dp[i][j] * j;
            }
            ans += f[i];
        }

Jetbrains全家桶1年46，售后保障稳定

但是这样是会TLE的，有<=1000组数据，L<=1000。复杂度为O(L^2),所以1000 * 1000 * 1000 = ……     = =#。。。。QAQ

我们先手算几个数据：

f[0] = 0;

f[1] = p;

f[2] = p + p * p;

f[3] = p + p * p + p * p * p;

.

.

.

发现f[i] = ∑p^k, k = 1, 2, …, i      (⊙v⊙)…

于是，

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 10;
double dp[maxn][maxn], f[maxn];
int L, T;
double p, ans;
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%lf", &L, &p);
        ans = 0.0;
        double tmp = p;
        for(int i=0; i<L; i++){
            ans += (L - i) * tmp;
            tmp *= p;
        }
//        dp[0][0] = 1.0;
//        f[0] = 0;
//        for(int i=1; i<=L; i++){
//            dp[i][0] = 1.0 - p;
//            f[i] = 0;
//            for(int j=1; j<=i; j++){
//                dp[i][j] = dp[i - 1][j - 1] * p;
//                f[i] += dp[i][j] * j;
//            }
//            ans += f[i];
//        }
        printf("%lf\n", ans);
    }
    return 0;
}

over~ (>^ω^<)喵~