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", n == 1 ? 1 : 2 * f[n]);58 ????} 59 ????return 0;60 } UVA10253 Series-Parallel Networks
原文地址：https://www.cnblogs.com/huibixiaoxing/p/8315365.html