题意:给定m-叉树(1<=m<=20)的前序和后续遍历,求出一共有多少满足条件的树。数据不会超int。
题解:中序+前序 -> 唯一的后序,中序 + 后序 -> 唯一的前序,但是前序 + 后序 -x> 中序,因为根是不固定的,明白这个就很容易想出这个问题了。
首先dfs确定每棵子树在前序和后序中对应的范围,然后统计子树个数,通过组合数求解即可。
Sure原创,转载请注明出处。
#include <iostream> #include <cstdio> #include <string.h> using namespace std; const int maxn = 30; int C[maxn][maxn]; char pre[maxn],post[maxn]; int n,m; void prepare() { memset(C,0,sizeof(C)); for(int i=0;i<maxn;i++) { C[i][0] = 1; } for(int i=1;i<maxn;i++) { for(int j=1;j<=i;j++) { C[i][j] = C[i-1][j-1] + C[i-1][j]; } } return; } int dfs(int rs,int rt,int os,int ot) { if(rs == rt) return 1; int son = 0,res = 1; int l = rs + 1,r = os; while(l <= rt) { while(r < ot) { if(pre[l] == post[r]) { son++; break; } r++; } res *= dfs(l , l + r - os , os , r); l += r - os + 1; rs = l - 1; os = ++r; } return res * C[m][son]; } int main() { prepare(); while(scanf("%d",&m) && m) { scanf("%s %s",pre,post); n = strlen(pre); printf("%d\n",dfs(0,n-1,0,n-1)); } return 0; }