一道巧妙的卡特兰数建模

题目

SKYLINE - Skyline

此题是左神的卡特兰数教程中的一道练习题目（这里强烈安利想学算法的同学可以看左神的教程），认真分析后发现实际上不难做，题意也很简单：

数字从1到n，可以形成很多排列，要求任意从左往右的三个位置，不能出现依次递增的样子。返回排列的方法数。也就是说不存在 $i<j<k$ 并且满足 $a[i]<a[j]<a[k]$。

思路

这道题目我首先的想法是用经典的卡特兰数模型去做一个映射，但是发现其中的问题结构和卡特兰数经典的组合结构差很多。

首先我们可以明确一点，$n$个数字的所有合法序列一定是从$n-1$个数字的合法序列中某个位置插入$n$得到（这个证明不难，这里省略）。

所以我们不妨枚举其中的最大的数字的位置来找一下规律，而且可以得知，最大数字的左边的所有数字一定是单调递减的（不然一定不合法），所以我们给合法的序列规定一个最长单调递减前缀的长度，举个例子：

$3,2,1$的最长单调递减前缀长度是3，$2,1,4$的最长单调递减前缀长度是2，以此类推，这个在后面会有用。

构造

$n=1$的时候，我们只有一种合法的序列：

$$1$$

$n=2$的时候，我们可以枚举2的位置，得到一个合法的序列：

$$\begin{gathered} 2,1 \\ 1,2 \end{gathered}$$

$n=3$的时候，我们继续枚举3的位置，如果放在第一个位置上，就有：

$$\begin{gathered} 3,2,1 \\ 3,1,2 \end{gathered}$$

都是合法的，如果放在第二个位置上，相当于插入了$n=2$的中间，则有：

$$\begin{gathered} 2,3,1 \\ 1,3,2 \end{gathered}$$

也都是合法的，那么我们放到$n=2$的合法序列的最后面呢？

$$\begin{gathered} 2,1,3 \\ 1,2,3 \end{gathered}$$

这个时候我们就会发现了，$1,2,3$不合法！最重要的原因其实就是$1,2$没有单调递减。而这也说明了一个非常重要的讯息：

对于$n-1$个数字构成的最长单调递减前缀长度为$L$的合法序列，最多能够贡献$L+1$个$n$个数字的合法序列。比如说下面这个例子：

序列$3,2,1$，对于$4$，$4$可以放到其中任何一个位置，得到：

$$\begin{gathered} 4,3,2,1 \\ 3,4,2,1 \\ 3,2,4,1 \\ 3,2,1,4 \end{gathered}$$

本质就是$4$的左边都是单调递减的。而对于序列$2,1,3$而言，就只能得到以下的合法序列：

$$\begin{gathered} 4,2,1,3 \\ 2,4,1,3 \\ 2,1,4,3 \end{gathered}$$

因此，我们将这个问题转换为了维护合法序列的最长单调递减长度的问题。

维护

首先我们可以分析，$n$个数字的合法序列中，最长单调递减长度$L$为1的合法序列有哪些？其实就是$n-1$个数字的合法序列的数量。构造方法就是将$n$放在所有序列的第一个数字后面。同理，$L$为2的合法序列长度等于$n-1$个数字的合法序列中的所有$L\ge 2$的序列，构造方法就是放在第二个数字后面，以此类推。但是这里需要注意一点，如果将$n$放在序列的第一个位置，那么一定能够使得所有序列的$L$增加1，因此最后还要加上去，所以结论就是$n$个数字的合法序列的最长单调递减长度为$L$的合法序列个数等于$n-1$个数字中的合法序列最长单调递减长度为$x\ge L-1$的合法序列数量之和 。下面举例子说明：

这是$n=3$的所有合法序列以及$L$的信息：

其中的$L$的信息可以得到：

那么我们其实就可以了构造关于$n=4$的$L$表了（前缀和），先算$n$不放在最前面的：

$L=1$的情况，有$2+2+1=5$种。
$L=2$的情况，有$2+1=3$种。
$L=3$的情况，有$1$种。
$L=4$的情况，有$0$种。

然后还有一种将$n$放到最前面，这样将会使得我们现在的长度为$L$的合法序列，加上之前的长度为$L-1$的合法序列个数：

$L=1$的情况，有$5$种。
$L=2$的情况，有$3+2=5$种。
$L=3$的情况，有$1+2=3$种。
$L=4$的情况，有$1$种。

实际上可以使用上面的结论一步算完：

$L=1$的情况，对应$x\ge 0$，有$2+2+1=5$种。
$L=2$的情况，对应$x\ge 1$，有$2+2+1=5$种。
$L=3$的情况，对应$x\ge 2$，有$1+2=3$种。
$L=4$的情况，对应$x\ge 3$，有$1$种。

可以得到下面的表：

$n$个数字对应的合法序列个数就是以上的$number$的和。

卡特兰数建模

上面的$L$表维护过程实际上可以用图可视化一下（$n=6$）：

$$\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 2& 2& 1\\ 0& 0& 5& 5& 3& 1\\ 0& 14& 14& 9& 4& 1\\ 42& 42& 28& 14& 5& 1\end{array}\right]$$

我们其实可以很容易发现，对于$f[i][j]=f[i-1][j]+f[i][j+1]$，为什么呢？我们不妨这样看，第一行第一个1代表就是$L=1$的数量，第二行从左往右分别代表$L$从$1$到$2$的数量，第三行从左到右分别代表$L$从$1$到$3$的数量，以此类推。那么根据我们上面讨论的结论，可知：

$$f[i][j]=\sum _{k=j}^{k=i-1}f[i-1][k]=f[i-1][j]+\sum _{k=j+1}^{k=i-1}f[i-1][k]=f[i-1][j]+f[i][j+1]$$

得到这个表达式之后，那么这道题就很显然和卡特兰数的路径计数模型相关了！因为上面的矩阵的结果就是等于你每一步只能向下走或者向左走且不能超过对角线的方法数量！不能超过对角线的走法也就意味着任意时刻向下走的次数大于等于向左走，而这也就是卡特兰数的经典模型，所有后面也就不再赘述了，不懂的强烈推荐看看左神教程。