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

发表于 | 分类于 | | + s

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

#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;
}
------ 本文结束 ------