『金字塔区间dp』

傷城~ 2021-12-21 21:09 311阅读 0赞

--------------------

## 金字塔 ##

### Description ###

虽然探索金字塔是极其老套的剧情，但是这一队 探险家还是到了某金字塔脚下。经过多年的研究，科 学家对这座金字塔的内部结构已经有所了解。首先， 金字塔由若干房间组成，房间之间连有通道。如果把 房间看做节点，通道看做边的话，整个金字塔呈现一 个有根树结构，节点的子树之间有序，金字塔有唯一 的一个入口通向树根。并且，每个房间的墙壁都涂有 若干种颜色的一种。

探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。这 种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。机器人每进入一个房间（无 论是第一次进入还是返回），都会记录这个房间的颜色。最后，机器人会从入口退出金字塔。 显然，机器人会访问每个房间至少一次，并且穿越每条通道恰好两次（两个方向各一次）， 然后，机器人会得到一个颜色序列。但是，探险队员发现这个颜色序列并不能唯一确定金字 塔的结构。现在他们想请你帮助他们计算，对于一个给定的颜色序列，有多少种可能的结构 会得到这个序列。由于结果可能会非常大，你只需要输出答案对10^9 取模之后的值。

### Input Format ###

输入文件包含一行，含有一个字符串，表示机器人得到的颜色序列。

### Output Format ###

输出一个整数表示答案。

### Sample Input ###

ABABABA

### Sample Output ###

### 解析 ###

在树形结构中，一棵子树可以对应一个序列区间上的区间，所以不难想到可以使用区间\\(dp\\)来计数，状态即为：\\(f\[l\]\[r\]\\)代表字符串中\\(\[l,r\]\\)这一段对应的方案数。

对于区间\\(\[l,r\]\\)所对应的子树，我们考虑如何进行划分。显然，对应的一个根节点棵可能有很多个子节点，如果枚举每一个子树的划分点就会超时，换一种思路，我们枚举区间\\(\[l,r\]\\)第一棵子树的位置，假设有划分点\\(mid\\)，且\\(s\[l\]=s\[mid\]\\)，则\\(\[l+1,mid-1\]\\)就恰好可以对应一个子树，\\(s\[l\]\\)和\\(s\[mid\]\\)就是进出时产生的字符。而剩余部分\\(\[mid,r\]\\)也就刚好对应了一个子问题，直接将方案数累加即可。

\\(Code:\\)

#include<bits/stdc++.h> using namespace std; const int N = 320 , Mod = 1e9; int n; char a[N]; long long f[N][N]; inline void input(void) { scanf("%s",a+1); n = strlen( a+1 ); } inline void dp(void) { memset( f , 0x00 , sizeof f ); for (int i=1;i<=n;i++) f[i][i] = 1; for (int len=3;len<=n;len++) { for (int l=1;l+len-1<=n;l++) { int r = l+len-1; if ( a[l] != a[r] ) continue; f[l][r] = f[l+1][r-1]; for (int mid=l+2;mid<=r-2;mid++) if ( a[l] == a[mid] ) f[l][r] = ( f[l][r] + f[l+1][mid-1] * f[mid][r] % Mod ) % Mod; } } } int main(void) { input(); dp(); printf("%lld\n",f[1][n]); return 0; }

--------------------

转载于:https://www.cnblogs.com/Parsnip/p/10999815.html