金字塔（区间dp）

题目描述

链接

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

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

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

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

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

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

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

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

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

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

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

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

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

输入描述:

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

输出描述:

输出一个整数表示答案。

输入

ABABABA
           

输出

思路

之前做的区间dp题目都是：一个大区间可以看作是两个小区间合并。

如果这道题规定，金字塔内部结构是一棵二叉树，那么和普通的区间dp就一样了（因为一个区间最多可以看作是两个区间合并）。

可是它是多叉树，区间dp的时候要合并多个区间就没法搞了。

STD是，确定第一棵子树 d f s dfs dfs 序的范围。 也就是说，本来是多个区间合并，把它看作是第一个区间和剩下的所有区间合并。

这样枚举第一个区间的范围，就不会漏解。而且又转化为我们熟悉的两个区间合并了。

f [ i ] [ j ] = ∑ s [ i ] = s [ k ] , i ≤ k ≤ j f [ i + 1 ] [ k − 1 ] × f [ k ] [ j ] f[i][j]=\sum_{s[i]=s[k],i \le k \le j} f[i+1][k-1] \times f[k][j] f[i][j]=s[i]=s[k],i≤k≤j∑​f[i+1][k−1]×f[k][j]

#include<bits/stdc++.h>
using namespace std;
const int N=310,mod=1e9;
char s[N]; int n,f[N][N];

signed main(){
	cin>>(s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) f[i][i]=1;
	for(int len=2;len<=n;len++)
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			for(int k=i;k<=j;k++) if(s[i]==s[k])
				f[i][j]=(f[i][j]+f[i+1][k-1]*f[k][j])%mod;
		}
	cout<<f[1][n]<<"\n";
}