CF1906J Count BFS Graph

题意

对于一个简单无向图，我们以 $1$ 为起点对其进行 BFS，规定对于一个结点，其相邻结点入队时按编号从小到大入队。这样会得到唯一的 BFS 序。

给出一个长度为 $n$ 的 BFS 序 $a$，求有多少张 $n$ 个点不同的简单无向图使得其 BFS 序为 $a$。

$n\le5000$。

题解

发现很像这道题。

同样考虑 dp，令 $dp_{i,j}$ 为队头为 $a_j$ 且队尾为 $a_k$ 时的方案数。

考虑用 $dp_{i,j}$ 更新别人。我们可以枚举点 $a_i$ 使哪些点新入队。

设扩展完点 $a_i$ 后，队尾变成 $k(k\ge j)$。

如果 $k=j$，则一个点都没有扩展到，则有转移：

首先必须满足 $a_{j+1}<a_{j+2}<\cdots<a_k$。（因为同一个点更新是从小到大入队）

然后，