UVA10253 Series-Parallel Networks

Series-Parallel Networks

https://vjudge.net/problem/UVA-10253

如果用一个节点表示串联/并联操作，用一棵树表示每一个串并联网络，要求一个节点代表的串并联网络全部按照这个节点表示的方式(串联/并联）拆开成为他的子节点

不难发现除了叶子节点为单边串并联网络外，第一层若为串，第二层就是并，第三层是串....

或者第一层为并，第二层为串，第三层为并.......

其实就是给你n个叶子节点，问你能组成多少颗叶节点数>=2的树

dp[i][j]表示叶节点数最大为i，有j个叶节点的方案数

考虑i个叶节点的节点有p个

dp[i][j] = sum{dp[i - 1][j - p * i] * C(f[i] + p - 1, p)}

蓝书上的边界很难以理解。。我是这样做得边界

dp[1][i] = 1，因为每个节点最多有1个叶子，由于每个节点至少有两个儿子，因此相当于除根节点外每个节点最多有0个叶子，方案就是根节点连所有叶子
dp[i][0] = 1,i >= 1，因为如果有状态转移到这里的时候，意味着叶节点全部在叶节点最大的子树中，情况可行，*1即可

dp[i][1] = 1,i >= 1，显然

被奇怪的边界设定卡的要死

感觉我这样的边界设定比书上好理解多吧。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <cmath> 
 9 #define min(a, b) ((a) < (b) ? (a) : (b))
10 #define max(a, b) ((a) > (b) ? (a) : (b))
11 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
12 inline void swap(long long &a, long long &b)
13 {
14     long long tmp = a;a = b;b = tmp;
15 }
16 inline void read(long long &x)
17 {
18     x = 0;char ch = getchar(), c = ch;
19     while(ch < '0' || ch > '9') c = ch, ch = getchar();
20     while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();
21     if(c == '-') x = -x;
22 }
23 
24 const long long INF = 0x3f3f3f3f;
25 const long long MAXN = 30;
26 
27 long long f[MAXN + 50], dp[MAXN + 50][MAXN + 50], n;
28 
29 long long tma,tn,tm;
30 
31 double ma;
32 
33 long long C(long long n, long long m)
34 {
35     long long ans = 1;
36     for(register long long i = n;i >= n - m + 1;-- i) ans *= i;
37     for(register long long i = 2;i <= m;++ i) ans /= i;
38     return ans;
39 }
40 
41 int main()
42 {
43     for(register long long i = 1;i <= MAXN;++ i) dp[i][0] = 1;
44     for(register long long i = 1;i <= MAXN;++ i) dp[i][1] = 1;
45     f[1] = 1;
46     for(register int i = 0;i <= MAXN;++ i) dp[1][i] = 1;
47     for(register long long i = 2;i < MAXN;++ i)
48     {
49         f[i] = dp[i - 1][i];
50         for(register long long j = 2;j <= MAXN;++ j)
51             for(register long long p = 0;j >= p * i;++ p)
52                 dp[i][j] += C(f[i] + p - 1, p) * dp[i - 1][j - p * i];
53     }
54     f[MAXN] = dp[MAXN - 1][MAXN];
55     while(scanf("%lld", &n) != EOF && n)
56     {
57         printf("%lld
", n == 1 ? 1 : 2 * f[n]);
58     } 
59     return 0;
60 }

UVA10253