「CH 5302」金字塔

「Link」

一道 trivial 的 DP

定义 $f_{i, j}$ 为序列为 $s_{i\dots j}$ 的树的个数

$s_i\neq s_j$ 显然 $f_{i,j}=0$

考虑如何处理 $f_{i,j}$

• $i=j$ 就是只有一个节点
• 有一个或多个子节点，考虑第一个子树是在哪里断

具体来说，考虑所有 $s_k=s_i=s_j(i<k\le r)$

钦定 $s_{i+1\dots k-1}$ 为一棵子树

其余的丢到以后考虑

$$f_{i,j}=\sum_{i<k\le j,s_k=s_i} f_{i+1, k-1}\cdot f_{k,j}$$

记忆化搜索

const int MOD = 1e9;
int f[N][N];

int calc(int l, int r) {
    // cerr << l << ' ' << r << endl;
    if (f[l][r] != -1) return f[l][r];
    if (l == r) return f[l][r] = 1;
    int ret = 0;
    rep(k, l + 1, r) {
        if (s[k] == s[l]) {
            (ret += (ll)calc(l + 1, k - 1) * calc(k, r) % MOD) %= MOD;
        }
    }
    return f[l][r] = ret;
}

递推

rep(i, 1, n) f[i][i] = 1;
for (int len = 2; len <= n; len += 2) // 事实证明长度肯定为奇数
    rep(i, 1, n - len){
        int j = i + len;
        rep(k, i + 1, j)
            if (s[i] == s[k])
                (f[i][j] += (ll)f[i + 1][k - 1] * f[k][j] % MOD) %= MOD;
    }

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;

const int N = 310;
char s[N];

const int MOD = 1e9;
int f[N][N];

// int calc(int l, int r) {
//     // cerr << l << ' ' << r << endl;
//     if (f[l][r] != -1) return f[l][r];
//     if (l == r) return f[l][r] = 1;
//     int ret = 0;
//     rep(k, l + 1, r) {
//         if (s[k] == s[l]) {
//             (ret += (ll)calc(l + 1, k - 1) * calc(k, r) % MOD) %= MOD;
//         }
//     }
//     return f[l][r] = ret;
// }

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    cin >> s + 1;
    int n = strlen(s + 1);
    rep(i, 1, n) f[i][i] = 1;
    for (int len = 2; len <= n; len += 2) {
        rep(i, 1, n - len) {
            int j = i + len;
            rep(k, i + 1, j) {
                if (s[i] == s[k]) {
                    (f[i][j] += (ll)f[i + 1][k - 1] * f[k][j] % MOD) %= MOD;
                }
            }
        }
    }
    cout << f[1][n];
    // std::memset(f, -1, sizeof(f));
    // cout << calc(1, n);
    return 0;
}