一个序列长度是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.net/234872.html原文链接：https://javaforall.net
