题目描述

给你一个字符串，并且告诉你这个是一棵树的一次 DFS 遍历序列，使用颜色标记节点，并且不保证每个节点颜色不同，也就是存在相同颜色的节点。
你需要输出合法的树结构存在几个？

Solition

首先这是一个类 DFS 序，那么是不是可以得到结论，使用区间 [ l, r] 构造的树，一定会存在一些分割点 k ，使得 s[l] = s[k]，只有这样才能满足DFS的回溯条件。
那么我们是不是就可以使用区间DP去处理这个问题了。如果假设 dp[i][j] 代表以i位置为根，j位置结束的合法树结构数目。那么初值就是dp[i][i]=1。
接下来只需要枚举奇数区间，因为不存在那个合法的DFS回溯会存在偶数长度。
如果区间端点都不相同，直接continue掉这个区间，直到找到一个区间是符合要求的。那么我们就可以去枚举分割点了。
但是这个分割点如果只有s[r]的时候。也就是ABA的情况，只有一颗子树。那么我初步直接让 dp[l][r] = dp[l+1][r-1]就可以处理掉这个情况。
接着在 [ l+2, r-2]区间去枚举可能正确的分割点累加（左边一个子树乘上右边一个子树的情况）即可，左子数的根是 l+1, 右子树的根是分割点 k
例如 ABABA 下标1开始的化，可以枚举3作为分割点，dp[1][5]+= dp[2][2] * dp[3][5]，相当于先序遍历，依次变换最左边的子树的形状，保证答案不重复。
下面也有我之前写的记忆化搜索，区间dp和记忆化搜索都是类似的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
const int MOD = 1e9;
const int N = 300 + 7;

ll dp[N][N];
char s[N];

int main() {
    int T = 1;
    //T = read();
    while (T--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        for (int i = 1; i <= n; ++i)    dp[i][i] = 1;
        for (int len = 3; len <= n; len += 2) {
            for (int l = 1, r = l + len - 1; r <= n; ++l, ++r) {
                if (s[l] != s[r])    continue;
                dp[l][r] = dp[l + 1][r - 1];
                for (int k = l + 2; k <= r - 2; ++k)
                    if (s[l] == s[k])
                        dp[l][r] = (dp[l][r] + dp[l + 1][k - 1] * dp[k][r]) % MOD;
            }
        }
        print(dp[1][n]);
    }
    return 0;
}

/*
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

const int N = 300 + 7;
const int MOD = 1e9;

ll dp[N][N];
char s[N];

ll dfs(int l, int r) {
    if (l > r)    return 0;
    if (l == r)    return 1;
    if (dp[l][r] != -1)    return dp[l][r];
    dp[l][r] = 0;
    for (int i = l + 1; i < r; ++i)
        if (s[l] == s[i + 1])
            (dp[l][r] += dfs(l + 1, i) * dfs(i + 1, r) % MOD) %= MOD;
    return dp[l][r];
}

int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%s", s + 1);
    printf("%lld\n", dfs(1, strlen(s + 1)));
    return 0;
}
*/