Exploring Pyramids UVALive - 3516 多叉树遍历-CSDN博客

本文链接：https://blog.csdn.net/qq_42835910/article/details/90245455

本文探讨了基于特定访问序列计算符合该序列的多叉树数量的问题，通过动态规划算法实现，介绍了递推关系和边界条件，适用于算法竞赛和数据结构学习。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

给出一棵多叉树，每个结点的任意两个子结点都有左右之分。从根结点开始，每次尽量往左走，走不通了就回溯，把遇到的字母顺次记录下来，可以得到一个序列。如图2-6所示的5 个图的序列均为ABABABA 。给定一个序列，问有多少棵树与之对应。

【输入格式】
输入包含多组数据。每组数据仅一行，即由大写字母组成的访问序列。序列非空，且长度不超过300 。输入结束标志为文件结束符（EOF) 。
【输出格式】
对于每组数据，输出满足条件的多叉树的数目除以10^9 的余数。
【分析】
设输入序列为S，d(i，j)为子序列Si,Si+1,.....Sj与对应的树的个数，则边界条件是d(i，i)=1，且Si 不等于Sj时d(i,j)=0( 因为起点和终点应是同一点)。在其他情况下，设第一个分支在Sk 时回到树根(必须有Si = Sk) ，则这个分支对应的序列是Si+1,...Sk-1,方案数为d(i+1,k-1);
其他分支对应的访问序列为Sk,...Sj，方案数为d(kJ) 。这样，在非边界情况，递推关系为
，如图2-7 所示。

#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 300 + 10;
const int MOD = 1000000000;
typedef long long LL;

char S[maxn];
int d[maxn][maxn];

int dp(int i, int j) {
  int& ans = d[i][j];
  if(ans >= 0) return ans;
  if(i == j) return ans = 1;
  if(S[i] != S[j]) return ans = 0;
  ans = 0;
  for(int k = i+2; k <= j; k++) if(S[i] == S[k])
    ans = (ans + (LL)dp(i+1,k-1) * (LL)dp(k,j)) % MOD;
  return ans;
}

int main() {
  while(scanf("%s", S) == 1) {
    memset(d, -1, sizeof(d));
    printf("%d\n", dp(0, strlen(S)-1));
  }
  return 0;
}