LUOGU P3830 [SHOI2012]随机树

传送门

解题思路

一道比较好的期望dp题,对于第一问来说,设f[i]表示有i个叶子节点的平均叶子深度,当展开一次,它的影响是对于某棵树的某个叶子来说让他的总叶节点数+这个叶子的深度再+2,因为不知道是哪个叶子展开,直接算太麻烦,所以这个叶子的深度其实就相当于平均值,这点比较巧妙,也就是说直接+一个平均值+2即可,所以转移方程为f[i]=(f[i-1](i-1)+f[i-1]+2)/i ,f[i-1](i-1)就是总的叶子节点的深度,这个式子化简一下就是f[i]=f[i-1]+2/i,最后的答案则是f[n]。对于第二问有两种解法,设g[x]表示有x个叶节点的期望树深,那么g[x]=max(g[左子树],g[右子树])+1,但这样是不对的,因为这样不知道左右节点的具体有几个,每个多深,所以还要记录一维,设g[i][j] 为i个叶节点,树高为j的期望,然后枚举一个深度,一个左儿子,一个左深度,一个右深度就可以转移,时间复杂度O(n^4),但是是能过的。第二种解法是在某个大佬的博客上看见的,状态设计比较巧妙,g[i][j] 表示有i个叶节点树深>=j的期望,这样转移方程为:g[i][j] =(g[k][j-1]+g[i-k][j-1]-g[k][j-1]*g[i-k][j-1])/(i-1),j表示枚举的树深,k表示左儿子,意思就是左右两边只要有一个儿子的树深>=j-1就可以转移,但是要减去重复的部分,最后答案为g[n][i]的和,时间复杂度O(n^3)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int MAXN = 105;

int q,n;
double f[MAXN],ans;  //f[i]表示有i个节点的叶子节点的期望 
double g[MAXN][MAXN]; 
int main(){
    scanf("%d%d",&q,&n);
    if(q==1){
        f[1]=0.0;
        for(register int i=2;i<=n;i++)
            f[i]=f[i-1]+2.0/i;
        printf("%.6lf",f[n]);
    }
    else{
//      for(register int i=1;i<=n;i++) g[i][0]=1.0;
//      for(register int i=2;i<=n;i++)
//          for(register int j=1;j<i;j++){
//              double sum=0;
//              for(register int k=1;k<i;k++)   
//                  sum+=g[k][j-1]+g[i-k][j-1]-g[k][j-1]*g[i-k][j-1];
//              g[i][j]=sum/(i-1);  
//          }
//      for(register int i=1;i<=n;i++)
//          ans+=g[n][i];
//      printf("%.6lf",ans);
        g[1][0]=1;
        for(register int i=2;i<=n;i++)
            for(register int j=1;j<i;j++)   
                for(register int k=0;k<i;k++)
                    for(register int l=0;l<i;l++)
                        g[i][max(l,k)+1]+=g[j][l]*g[i-j][k]/(i-1);
        for(register int i=1;i<=n;i++)
            ans+=g[n][i]*i;
        printf("%.6lf",ans);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/sdfzsyq/p/9676858.html