区间$dp$解决树的个数的经典问题。
感觉自己对$dp$还是不太敏感，将信息分段重整的能力还不是很强
1
| 给定一颗树的先序遍历，问有多少棵树的先序遍历和它一样
|
Solution
首先记$f_{i,j}$表示将$i \sim j$组成一颗以$i$为根节点的树的合法方案数，同时设$g_{i,j}$表示将$i\sim j$中的树划分成多个合法的子树的方案数。
那么显然有方程：$f_{i,j}=f_{i+1,j}+g_{i+1,j}$。
而对于$g$，发现左右区间都有多个子树时并不是那么好合并（不知道最劣的子树是哪个），所以我们考虑先找到一颗最小的子树，在将其他的多颗子树的方案往上合并（仔细思考发现和上面的结果是一样的），而且由于最优的根节点一定在最左边，所以我们只用比较两个区间左端点就行了。
$$
g_{i,j}=\sum_{l\le k < r}f_{i,k}\cdot (f_{k+1,r}+g_{k+1,r}),\forall k,a_i<a_{k+1}
$$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cstdio>
#define LL long long
#define uLL unsigned LL
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while('0' > c || c > '9'){ if(c == '-') flag = 1; c = getchar(); }
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
inline void write(char c) { putchar(c); }
inline void write(const char *s) { while(*s) putchar(*s ++); }
template <class T>
inline void write(T res)
{
if(res < 0) putchar('-'), res = -res;
if(res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 505, mod = 998244353;
int n;
int a[N];
int f[N][N][2];
int main()
{
read(n);
for(int i = 1;i <= n;i ++) read(a[i]);
for(int i = 1;i <= n;i ++) f[i][i][0] = 1;
for(int len = 2;len <= n;len ++)
{
for(int l = 1, r;l + len - 1 <= n;l ++)
{
r = l + len - 1;
f[l][r][0] = (f[l + 1][r][0] + f[l + 1][r][1]) % mod;
for(int k = l;k < r;k ++)
if(a[l] < a[k + 1]) f[l][r][1] = (f[l][r][1] + 1ll * f[l][k][0] * (f[k + 1][r][0] + f[k + 1][r][1]) % mod) % mod;
}
}
write(f[1][n][0]);
return 0;
}
|