例题：金字塔 解题报告（区间DP）

5302 金字塔 0x50「动态规划」例题

描述

虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。首先，金字塔由若干房间组成，房间之间连有通道。如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。并且，每个房间的墙壁都涂有若干种颜色的一种。
探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。机器人每进入一个房间（无论是第一次进入还是返回），都会记录这个房间的颜色。最后，机器人会从入口退出金字塔。
显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。但是，探险队员发现这个颜色序列并不能唯一确定金字塔的结构。现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构会得到这个序列。因为结果可能会非常大，你只需要输出答案对10^9 取模之后的值。

输入格式

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

输出格式

输出一个整数表示答案。

样例输入

ABABABA

样例输出

5

样例解释

例如序列“ABABABA”对应5种金字塔结构，最底部是树根。我们认为子树之间是有序的，所以方案3和4是两种不同的方案。如书中图所示。其中3和4是不同方案。

来源：《算法竞赛进阶指南》李煜东 P262

解题思路：

一棵树的每颗子树都对应着这棵树 DFS 序的一个区间。本题的序列虽然不是 DFS 序列，但也有该性质。本题中，我们以区间长度作为阶段， F[ l , r ] 表示序列 s[ l ~ r ]中子树的个数。

如果我们从 l  到  r  在每一个点划分一个 k ，那么时间复杂度会很高。一个比较好的想法是，把子串s[ l ~ r ]分成两部分，每部分可由若干子树构成。为了计数重而不漏，我们只考虑子串的第一颗子树是由哪些序列构成的，即令子串s[ l+1 ~ k-1 ] 构成第一棵子树，s[ k~r ]构成剩余部分。

为什么这样不会重复呢？因为我们 k 不断向后移动，序列不断加长，也就是说第一颗子树规模在从小变大，当然不会重复；至于剩下部分构成的子树，同理，由于规模不断减小，不可能重复。

为什么还要加上一个F[ l + 1 , r - 1] 呢？因为我们虽然枚举了第一颗子树，但是却忽略了该树只有一颗子树的情况，所以需要再加上这种情况，即F[ l + 1 , r - 1 ]。

对于方案计数类的动态规划问题，通常一个状态的各个决策之间满足“加法原理”，而每个决策划分的几个子状态之间满足“乘法原理”。在设计状态转移方程的决策方式与划分方法时，一个状态的所有决策之间必须具有互斥性，才能保证不会出现重复问题。

代码示例：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const ll Mod = 1e9;
const int maxn = 350;
char s[maxn];
ll f[maxn][maxn];
void solve(){
	int n = strlen(s);
	for(int i = 0;i <= n;i++) f[i][i] = 1;
	
	for(int len = 3;len <= n;len++){
		for(int l = 0;l + len-1 < n;l++){
			int r = l+len-1;
			if(s[l] != s[r]){
				f[l][r] = 0;
				continue;
			}
			f[l][r] = f[l+1][r-1];
			for(int k = l+2;k <= r-2;k++){
				if(s[l] == s[k])
					f[l][r] = (f[l][r] + f[l+1][k-1]*f[k][r]%Mod)%Mod;
			}
			//cout << l << " " << r << endl;
		}
	}
	cout << f[0][n-1]<<endl;
//	cout << n << endl;
}
int main(){
	scanf("%s",s);
	solve();
	return 0;
}