【每日一题】金字塔 题解(区间dp)

Description

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

Solution

对于dfs序, 由于题目的要求是进入还是返回都会记录颜色, 那么我们可以考虑把问题的规模进行缩小
令 代表以区间 可行的方案数。
显然 可以从 转化而来(大区间可以从小区间转移过来)
此外，根据dfs序的特性，当出现 的时候，可以令l为根，使得 作为以l为根的深度优先遍历的结果。
最后，我们可以枚举一个中间点 ， 如果出现 ，证明可以把 划分成两个子树, , 所以是 （两个子树的方案都可以随意排列组合）

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9;
int dp[305][305];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    string s; cin >> s;
    int n = s.size();
    s = ' ' + s;
    for(int i = 1; i <= n; i++) {
        dp[i][i] = 1;
    }
    for(int len = 2; len <= n; len++) {
        for(int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if(s[l] != s[r]) continue;
            dp[l][r] = dp[l + 1][r - 1];
            for(int mid = l + 1; mid <= r - 1; mid++) {
                if(s[l] == s[mid]) {
                    dp[l][r] += 1LL * dp[l + 1][mid - 1] * dp[mid][r] % mod;
                    dp[l][r] %= mod;
                } 
            }
        }
    }
    cout << dp[1][n] << '\n';
    return 0;
}