「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_{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;
}

------ 本文结束 ------