UVa 10253 (组合数 递推) Series-Parallel Networks

《训练之南》上的例题难度真心不小，勉强能看懂解析，其思路实在是意想不到。

题目虽然说得千奇百怪，但最终还是要转化成我们熟悉的东西。

经过书上的神分析，最终将所求变为：

共n个叶子，每个非叶节点至少有两个子节点的 树的个数f(n)。最终输出2 × f(n)

首先可以枚举一下根节点的子树的叶子个数，对于有i个叶子的子树，共有f(i)种，

设d(i, j)表示每棵子树最多有i个叶节点，一共有j个叶节点的方案数。

所求答案为d(n-1, n)

假设恰好有i个叶子的子树有p棵，因为每个子树互相独立，所以对于p个有i个叶子的子树，共有C(f(i)+p-1, p)种情况，重复元素的全排列。

d(i, j) = sum{C(f(i)+p-1, p) × d(i-1, j-p×i) | p >= 0 且 p×i <= j }

边界：

d(i, 0) = d(i, 1) = 1 (i >= 1), d(0, 0) = 1

 #include <cstdio>

 const int maxn = ;

 long long d[][], f[];

 long long C(long long n, long long m)

 {

     long long ans = ;

     if(m > n - m) m = n - m;

     for(int i = ; i < m; i++)

     {

         ans *= n - i;

         ans /= i+;

     }

     return ans;

 }

 int main()

 {

     f[] = ;

     int n = maxn;

     d[][] = ;

     for(int i = ; i <= n; i++) d[i][] = d[i][] = ;

     for(int i = ; i <= n; i++)

     {

         for(int j = ; j <= n; j++)

         {

             for(int p = ; p * i <= j; p++)

                 d[i][j] += C(f[i]+p-, p) * d[i-][j-p*i];

         }

         f[i+] = d[i][i+];

     }

     while(scanf("%d", &n) ==  && n)

         printf("%lld\n", n ==  ?  : f[n] * );

     return ;

 }

代码君