金字塔（区间DP或记忆化搜索）

题目：

给一个类似序的序列。（经过一个结点记录一次颜色）。问有多少棵有根树满足（结点子树之间有序）。答案输出。

做法：

设为序列区间对应有根树的方案数，答案即为。
转移思路：我们枚举区间对应的有根树里，第一棵子树的区间，设为，则其他子树对应区间。
不难发现，合法的转移中，此时有
最后加上只有一棵子树的情况：
区间或记忆化搜索都能写，个人喜欢写。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 310;
const ll mod = 1e9;
char s[N];
ll dp[N][N];
ll dfs(int l, int r){
    if (~dp[l][r]) return dp[l][r];
    ll &ans = dp[l][r] = 0;
    if (l == r) return ans = 1;
    if (s[l] != s[r]) return ans = 0;
    if ((r-l+1)%2 == 0) return ans = 0;
    if (r-l+1 == 3) return ans = 1;
    ans = dfs(l+1, r-1);
    for (int i = l+2; i <= r-2; i += 2){
        if (s[i] == s[l]){
            ll L = dfs(l+1, i-1), R = dfs(i, r);
            ans = (ans + L*R%mod)%mod;
        }
    }
    return ans;
}
int main(void){
    IOS;
    cin >> (s+1);
    int n = strlen(s+1);
    memset(dp, -1, sizeof dp);
    cout << dfs(1, n) << endl;
    return 0;
}