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 = 30;
long long d[31][31], f[31];

long long C(long long n, long long m)
{
    long long ans = 1;
    if(m > n - m) m = n - m;
    for(int i = 0; i < m; i++)
    {
        ans *= n - i;
        ans /= i+1;
    }
    return ans;
}

int main()
{
    f[1] = 1;
    int n = maxn;
    d[0][0] = 1;
    for(int i = 1; i <= n; i++) d[i][0] = d[i][1] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 2; j <= n; j++)
        {
            for(int p = 0; p * i <= j; p++)
                d[i][j] += C(f[i]+p-1, p) * d[i-1][j-p*i];
        }
        f[i+1] = d[i][i+1];
    }

    while(scanf("%d", &n) == 1 && n)
        printf("%lld
", n == 1 ? 1 : f[n] * 2);

    return 0;
}