蓝书例题之UVa 10253 Series-Parallel Networks

挺有趣的一道题
首先转化模型，思路参考蓝书，可得出等同于求共n个叶子，且每个非叶结点至少有两个子结点的无标号树的个数的二倍，设个数为(f[n])
考虑怎么求(f[n])，假设有一个(n)的整数划分，分别代表每棵子树中的叶节点个数，然后用可重组合，乘法原理和加法原理把(f[n])递推出来
这个过程可以用(dp)来完成，设(g[i][j])表示子树中叶结点数量最大值小于等于(i)，共有(j)个叶结点的树的个数，转移时枚举最大的叶结点数量(i)和叶结点数量为(i)的子树个数(k)，转移方程如下：

[g[i][j]=sumlimits_{k=0}^{kileqslant j}inom{f[i]+k-1}{k}g[i-1][j-ki] ]

然后(f[i]=g[i-1][i])
边界的设置比较神奇，我也不明白，直接把大刘的代码拿过来用了

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define N 30

ll C(ll n, ll m) {
  double ans = 1;
  for(ll i = n-m+1; i <= n; ++i) ans *= i;
  for(ll i = 1; i <= m; ++i) ans /= i;
  return (ll)(ans+0.5);
}

ll g[35][35], f[35];

int main() {
  f[1] = 1; //三个边界
  for(int i = 0; i <= N; ++i) g[i][0] = 1;
  for(int i = 1; i <= N; ++i) g[i][1] = 1;
  for(int i = 1; i <= N; ++i) {
    for(int j = 1; j <= N; ++j) {
      g[i][j] = 0;
      for(int k = 0; k*i <= j; ++k) g[i][j] += C(f[i]+k-1, k)*g[i-1][j-k*i];
    }
    f[i+1] = g[i][i+1];
  }
  int n;
  while(~scanf("%d", &n) && n) printf("%lld
", n == 1 ? 1 : 2*f[n]); //特判1，别忘乘以2
  return 0;
}