P10956 金字塔

题目描述

虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。

经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。

首先，金字塔由若干房间组成，房间之间连有通道。

如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。

并且，每个房间的墙壁都涂有若干种颜色的一种。

探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。

这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。

机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。

最后，机器人会从入口退出金字塔。

显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。

但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。

现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。

因为结果可能会非常大，你只需要输出答案对 $10^9$ 取模之后的值。

输入格式

输入仅一行，包含一个字符串 $S$，长度不超过 $300$，表示机器人得到的颜色序列。

输出格式

输出一个整数表示答案。

输入输出样例 #1

输入 #1

ABABABA

输出 #1

5

C++实现

#include<bits/stdc++.h>
#define int long long 
using namespace std;
string a;
int dp[305][305];
const int mod=1e9;
signed main()
{
	cin>>a;
	int n=a.size();
	a=" "+a;
	for(int i=1;i<=n;i++)
	{
		dp[i][i]=1;
	}
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			if(a[i]==a[j])
			{
				for(int k=i+1;k<j;k++)
				{
					if(a[k]==a[i])
					{
						dp[i][j]+=dp[i][k]*dp[k+1][j-1];
						dp[i][j]%=mod;
					}
				}
				dp[i][j]+=dp[i+1][j-1];
				dp[i][j]%=mod;
			}
		}
	}
	cout<<dp[1][n]<<'\n';
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容