POJ 2057 The lost house

这道题求的是期望。

首先，一看到期望，就会想到可以将问题分成若干个子问题，再分开算期望，所以这道题可以使用动态规划。

注意到每个叶子有房子的概率是均等的。所以答案就是遍历每个叶子最少的步数/叶子的总数。

所以问题划归为求遍历所有叶子的最少步数。

我们令fail[x]为以x为根的子树找不到房子的最少步数。

su[x]为以x为根的子树中找到房子最少步数。

le[x]为以x为根的子树中叶子的个数。

则有 fail[x]=sigma(fail[y]+2);(worm[x]=false) fail[x]=0 (worm[x]=true);

su[x]+=(fail[x]+1)*le[y]+su[y];(其中fail[x]为在y之前没有找到房子的步数）

显然，su[x]和x儿子的顺序是有很大关系的。

第一种想法是枚举所有的全排列。虽然每个节点只有最多8个儿子，但8！=40320，太大。

第二种想法是贪心。我们可以使用调整的思想来确定儿子的顺序。

设y1,y2为x的两个相邻的儿子。若y1在y2之前，则ans1=(fail[x]+1)*le[y1]+su[y1]+(fail[x]+2+fail[y1]+1)*le[y2]+su[y2]

若交换y1,y2，则有ans2=(fail[x]+1)*le[y2]+su[y2]+(fail[x]+2+fail[y2]+1)*le[y1]+su[y1]

则ans1-ans2=(fail[y1]+2)*le[y2]-(fail[y2]+2)-le[y1]。

所以可以根据这个排序。然后计算。

【总结】

求期望的题要注意搞清究竟要求什么，不要盲目上手，要想方设法的将问题化繁为简。像上述做法，整个过程中不涉及任何浮点运算，十分优秀。

【代码】

[cpp] 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <algorithm> 
#include <vector> 
using namespace std; 
 
const int N=1005; 
 
int su[N],fail[N],le[N],n,root; 
bool w[N]; 
vector<int> a[N]; 
 
bool cmp(int x,int y) 
{ 
    return (fail[x]+2)*le[y]<(fail[y]+2)*le[x]; 
} 
 
void dp(int x) 
{ 
    int i,y; 
    if (a[x].empty()) 
    { 
        le[x]=1; 
        return; 
    } 
    for (i=0;i<a[x].size();i++) 
    { 
        y=a[x][i]; 
        dp(y); 
        le[x]+=le[y]; 
    } 
    sort(a[x].begin(),a[x].end(),cmp); 
    for (i=0;i<a[x].size();i++) 
    { 
        y=a[x][i]; 
        su[x]+=(fail[x]+1)*le[y]+su[y]; 
        fail[x]+=fail[y]+2; 
    } 
    if (w[x]) fail[x]=0; 
} 
 
int main() 
{ 
    int i,j; 
    char ch; 
 
    freopen("in","r",stdin); 
    while (1) 
    { 
        scanf("%d",&n); 
        if (n==0) break; 
        memset(fail,0,sizeof(fail)); 
        memset(su,0,sizeof(su)); 
        memset(le,0,sizeof(le)); 
        memset(w,0,sizeof(w)); 
        for (i=1;i<=n;i++) 
            a[i].clear(); 
        for (i=1;i<=n;i++) 
        { 
            scanf("%d %c",&j,&ch); 
            if (j==-1) root=i; 
            else a[j].push_back(i); 
            w[i]=(ch=='Y'?true:false); 
        } 
        dp(root); 
        printf("%.4f/n",1.0*su[root]/le[root]); 
    } 
}