11/27周总结报告

上周学了概率dp的知识，这周为了更好的了解题目，先是看了相关的题，概率dp虽然没有固定的模板但是，解题方法还是有一些的，

首先是上次报告中说的类似分情况写概率的能直接写出期望的 题目： 2096 -- Collecting Bugs (poj.org)

D. Bag of mice 

这就是直接利用期望的定义公式来计算，

然后另一种是逆推来求期望，一般的例题如： 涂格子1   ， 【BZOJ】3036: 绿豆蛙的归宿

n个格子，每次随机涂一个，求涂满m个格子的期望次数。这种题一般是最终的状态已知，一般是求f[i]到终点n的期望长度   一般公式：f[i]=(f[j]+e[i].w)/k[i]  e[i].w表示对答案的贡献值，这个公式是根据全期望公式求得，我看的时候还不是很明白这个是怎么推来的，又因为是逆推所以可能会用到拓扑排序。

最后就是有的博客还总结了另一种方法就是期望的线性性质  E[X+Y]=E[X]+E[Y], 就是对每个期望分别求各分段的期望值，但是我看了那个例题  Codeforces 518D  那个方法其实 利用第一个也能求出来

for (int i = 0; i < t; ++i) {
        dp[i + 1][n] += dp[i][n];
        for (int j = 0; j < n; ++j) if (dp[i][j] > 1e-10) {
            dp[i + 1][j + 1] += dp[i][j] * p;
            dp[i + 1][j] += dp[i][j] * (1 - p);
        }
    }

最后也是开了一点树形dp的头

poj 2342 Anniversary party

 
void tree_dp(int node)
{
    int i;
    visited[node] = 1;
    for(i=1; i<=n; i++)
    {
        if(!visited[i]&&father[i] == node)//i为下属
        {
            tree_dp(i);//递归调用孩子结点，从叶子结点开始dp
            //关键
            dp[node][1] += dp[i][0];//上司来,下属不来
            dp[node][0] +=max(dp[i][1],dp[i][0]);//上司不来，下属来、不来
        }
    }
}

利用父节点的不同情况进行不同的概率计算的最后的期望