首页 > 代码库 > poj1240 Pre-Post-erous!
poj1240 Pre-Post-erous!
思路:
根据前序序列和后序序列递归构造m叉树,确定每个节点的子节点数量。再用组合数公式累乘。
实现:
1 #include <iostream> 2 using namespace std; 3 4 int m, c[25][25], ans = 1; 5 string x, y; 6 7 void init(int m) 8 { 9 c[0][0] = 1; 10 for (int i = 1; i <= m; i++) 11 { 12 c[i][0] = 1; 13 for (int j = 1; j <= i; j++) 14 c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; 15 } 16 } 17 18 void dfs(int lx, int rx, int ly, int ry) 19 { 20 if (lx > rx) return; 21 int cnt = 0; 22 while (lx <= rx) 23 { 24 int pos = ly; 25 while (pos < ry && y[pos] != x[lx]) pos++; 26 dfs(lx + 1, lx + pos - ly, ly, pos - 1); 27 lx += pos - ly + 1; 28 ly = pos + 1; 29 cnt++; 30 } 31 ans *= c[m][cnt]; 32 } 33 34 int main() 35 { 36 init(21); 37 while (cin >> m, m) 38 { 39 ans = 1; 40 cin >> x >> y; 41 int len = x.length(); 42 dfs(1, len - 1, 0, len - 2); 43 cout << ans << endl; 44 } 45 return 0; 46 }
poj1240 Pre-Post-erous!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。