感觉期望DP这种东西像是玄学…

主要总结说一点基础性的东西, 或许对于理解题目的做法会有一点帮助.

首先是关于独立事件, 互斥事件的概念. 通俗地说, 就是对于两个事件A, B, 假如满足发生了其中一个就不会发生另一个, 则称A, B为互斥事件; 假如A与B的发生没有任何关系, 可能都发生, 可能只有一个发生, 也可能都不发生, 则称A, B为独立事件. 下文的讨论主要针对独立事件进行.

一. 事件间的关系与运算;

A + B (和事件): 表示A, B两个事件至少有一个发生;

A · B(积事件)表示A, B两个事件同时发生;

二. 复杂事件的概率运算公式

和事件的概率: P(A + B) = P(A) + P(B) - P(A * B)

推广得到: P(A)=(P(A+B)−P(B))/(1−P(B))

即: P(A - B) = (P(A) - P(B)) / (1 - P(B))

适用于在知道和事件与其中一个事件的概率的情况下, 求另一个事件的概率.

特别地, 当A与B为互斥事件时, P(A + B) = P(A) + P(B)

积事件的概率: P(A1 * A2 * A3 * … * An) = P(A1) * P(A2) * … * P(An)

三. 期望值的计算公式:

Ex = ΣXiPi(ΣPi = 1)

例题: BZOJ3566概率充电器

这一题就用到了和公式与差公式

#include<cstdio>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

    int x = 0, flag = 1;

    char c;

    while(! isgraph(c = getchar()))

        if(c == '-')

            flag *= - 1;

    while(isgraph(c))

        x = x * 10 + c - '0', c = getchar();

    return x * flag;

}

void println(int x)

{

    if(x < 0)

        putchar('-'), x *= - 1;

    if(x == 0)

        putchar('0');

    int top = 0, ans[1 << 4];

    while(x)

        ans[top ++] = x % 10, x /= 10;

    for(; top; top --)

        putchar(ans[top - 1] + '0');

    putchar('\n');

}

const double EPS = 1e-8;

const int MAXN = 1 << 20;

int head[MAXN];

int top;

struct edge

{

    int v, next;

    double p;

}T[MAXN << 1];

void add_edge(int u, int v, double p)

{

    T[top].v = v, T[top].next = head[u], T[top].p = p, head[u] = top ++;

}

double q[MAXN];

double f[MAXN], ans[MAXN];

void DFS(int u, int fa)

{

    f[u] = q[u];

    for(int i = head[u]; i != - 1; i = T[i].next)

    {

        int v = T[i].v;

        if(v == fa)

            continue;

        DFS(v, u);

        f[u] = f[u] + f[v] * T[i].p - f[u] * f[v] * T[i].p;

    }

}

void DGS(int u, int fa)

{

    for(int i = head[u]; i != - 1; i = T[i].next)

    {

        int v = T[i].v;

        if(v == fa)

            continue;

        if(1 - f[v] * T[i].p < EPS)

                ans[v] = 1.0;

        else

        {

            double x = (ans[u] - f[v] * T[i].p) / (1 - f[v] * T[i].p) * T[i].p;

            ans[v] = f[v] + x - f[v] * x;

        }

        DGS(v, u);

    }

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("BZOJ3566.in", "r", stdin);

    freopen("BZOJ3566.out", "w", stdout);

    #endif

    int n = read();

    memset(head, - 1, sizeof(head));

    top = 0;

    for(int i = 1; i < n; i ++)

    {

        int a = read(), b = read(), p = read();

        add_edge(a, b, (double)p / 100.0);

        add_edge(b, a, (double)p / 100.0);

    }

    for(int i = 1; i <= n; i ++)

        q[i] = (double)read() / 100.0;

    memset(f, 0, sizeof(f));

    DFS(1, 1);

    ans[1] = f[1];

    DGS(1, 1);

    double sum = 0;;

    for(int i = 1; i <= n; i ++)

        sum += ans[i];

    printf("%.6f", sum);

}