Codeforces 235B(概率DP+组合数)

Codeforces 235B
这题可能一开始连状态都不知道怎么设,这里先给出一个结论,如果有一个O,那么分数加$1$,如果有两个O且之间没有X,那么分数加$2$.

我们来证明:
由$2C^2_n+n=n^2$
分两种情况
1 一个O的情况
在一个全是O序列中,O有$n$个
那么这些O对答案的贡献是$1$
这样完成就完成了一个O的情况的贡献
2 两个O的情况
在一个全是O序列中,两个O的情况有$C^2_n$种
我们设$event(j,i)$为$\prod_i^jp_x$,即$[j,i]$都是O的概率
因为这两个O之间不能有X,所以这两个O之间都必须是O,概率为$event(j,i)$
设$dp(i)=\sum_{j=1}^{i-1}event(j,i)$,每个$i$对答案的贡献为$dp(i) \times 2$
而算$dp(i)​$是平方级算法,并且这个$dp(i)​$没有充分利用前面的状态,我们试着推导:
$\sum_{j=1}^{i-1}event(j,i) = p_1 \times p_2 \times … \times p_i + p_2 \times p_3 \times … \times p_i + … + p_{i-1} \times p_i$
所以$dp(i)=(dp(i-1)+p_{i-1} \times p_i)$,就是把原式结合律
这样完成就完成了两个O的情况的贡献

然后把答案相加就是最后的答案。可以直接DP。然后观察方程,$dp(i)$只和$dp(i-1)$有关,所以数组都可以省了

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n;
void clean() {}
void solve() {
clean();
db tem = 0.0, p = 0.0, ans = 0.0;
for (int i=1;i<=n;i++) {
tem += p;
scanf("%lf", &p);
tem *= p;
ans += p + tem * 2;
}
printf("%.15f\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------