一个序列长度是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];
}
但是这样是会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~ (>^ω^<)喵~
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/234872.html原文链接:https://javaforall.cn