「CH 5302」金字塔 (区间DP)

CH 5302
题意：见上。
容易想到和加分二叉树差不多，但是这里复杂了很多，不是二叉树，而且也不是 DFS 序。
观察发现对于一个子树在这个序列中还是连续的一段，并且子树对应区间最前最后两个字符必须相同，等于根节点。所以我们可以设$dp(i,j)$为$[i,j]$的答案。
为了让计数不重复，我们分问题分为$[1,k-1]$只有一颗子树，$[k,j]$可以有多棵子树。那么转移
$$
dp(i,j)=
\begin{cases}
0, S[i] ≠ S[j]\\
\sum\limits_{i+2 \leq k \leq j, S[i]=S[k]} dp(i + 1, k - 1) \cdot dp(k, j), S[i]=S[j]
\end{cases}
$$
记忆化搜索即可。

知识点：
1、修改状态描述达到计数不重不漏

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky { 

    const int MAXN = 300 + 5;
    const LL MO = 1000000000ll;

    char s[MAXN];
    int n;
    LL f[MAXN][MAXN];

    LL dp(int l, int r) {
        if (l == r) return f[l][l] = 1ll;
        if (r < l) return f[l][r] = 0ll;
        if (f[l][r] >= 0ll) return f[l][r];
        if (s[l] != s[r]) return f[l][r] = 0ll;
        f[l][r] = 0ll;
        for (int k = l + 2; k <= r; ++k) if (s[l] == s[k]) {
            f[l][r] = (f[l][r] + dp(l + 1, k - 1) * dp(k, r) % MO) % MO;
        }
        return f[l][r];
    }

    void clean() {
        ms(f, -1);
    }
    int solve() {
        clean();
        scanf("%s", s + 1);
        n = strlen(s + 1);
        dp(1, n);
        cout << f[1][n];
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}