HDU1294 Rooted Trees Problem(整数划分 组合数学 DP)

讲解见http://www.cnblogs.com/IMGavin/p/5621370.html， 4 可重组合

dfs枚举子树的节点个数，相乘再累加

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 LL f[41];
 LL cm(LL n, LL m){
     m = min(n - m, m);
     LL ans = 1;
     for(LL i = 1; i <= m; i++){
         ans = ans * (n - m + i) / i;
     }
     return ans;
 }
 
 
 void dfs(int n, int x, int r, LL mul){
     if(r == 0){
         f[n] += mul;
 
     }else{
         for(int i = x; i < n; i++){
             for(int j = 1; i * j <= r; j++){
                 dfs(n, i + 1 , r - i * j, mul * cm(f[i] + j - 1,j ) );
             }
         }
 
     }
 }
 int main(){
     memset(f, 0  , sizeof(f));
     f[1] = 1;f[2] = 1;
     for(int i = 3; i <= 40; i++){
         dfs(i, 1, i - 1 ,1);
     }
 
     int n;
     while(~scanf("%d", &n)){
         printf("%I64d ", f[n]);
 
     }
     return 0;

46 }