hdu 5136(dp计数)

题目链接

题意：直径为K的每个点的边数不超过3的相互不同构的树有多少种？

解法：把树的直径拉开，两边就是两棵二叉树了。子问题：一个深度为m的不同构的二叉树有多少种？dp[i]表示深度为i的个数。sum[i]表示dp的前缀和。转移方程就是：dp[i+1]=dp[i]*sum[i-1]+dp[i]+dp[i]*(dp[i]-1)/2;

然后回到原问题：如果K是偶数（想象中间有个虚拟的不动点），则两边是两棵深度为K/2的二叉树，答案为：dp[i]*(dp[i]-1)/2+dp[i]

如果K为奇数，则中间还有一个节点：他也是颗二叉树，则分两种大情况：

第三个二叉树的深度小于K/2,则sum[K/2-1]*(dp[K/2]*(dp[K/2]-1)/2+dp[K/2])即可；

第三个二叉树的深度等于K/2,则分三类讨论：1 三棵二叉树结构一样dp[K/2] 2 两棵一样，2 另一棵不一样：dp[K/2]*(dp[K/2]-1) 3 三棵都不一样：dp[K/2]*(dp[K/2]-1)*(dp[K/2]-2)/6

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include