题解 P2532 【[AHOI2012]树屋阶梯】

syksykCCC · 2020-02-02 18:43:07 · 题解

发表一下自己关于这题是 卡特兰数 的观点。

我们用 C_i 表示 N = i 时的答案。

首先，显而易见，C_0 = C_1 = 1。

然后呢？我们画一张图:

图中所示是 N = 5 的情况。

然后我们看到阶梯的右侧是若干拐角，我们标一下号：

很容易发现，这里有 N 个拐角，而题目只允许我们放 N 个矩形，也就是说，每个矩形恰好覆盖一个拐角。

为啥？如果一个矩形覆盖的拐角 <1，那必然有矩形覆盖的拐角 >1。那么比如你的矩形覆盖了两个拐角，你不妨画一画那个矩形长成什么样子，自然就明白是不可能的了。

我们把最左下角叫做 o 点，它肯定要被一个矩形覆盖。

现在，我们枚举一下，覆盖 o 的矩形覆盖了哪一个拐角。

• 覆盖 1：

那么右边就是一个 N = 4 的子问题！方案数自然是 C_4，但也可以认为是 C_0 \times C_4。

• 覆盖 2：

上边就是 N = 1 的子问题，右边就是 N = 3 的子问题，根据乘法原理，方案数就是 C_1 \times C_3。

• 覆盖 3：

上边就是 N = 2 的子问题，右边就是 N = 2 的子问题，根据乘法原理，方案数就是 C_2 \times C_2。

• 覆盖 4：和覆盖 2 同理。

• 覆盖 5：和覆盖 1 同理。

于是，根据加法原理，我们就知道 C_5 = C_0 \times C_4 + C_1 \times C_3 + C_2 \times C_2 + C_3 \times C_1 + C_4 \times C_0。

更加的一般一点，我们就发现：

这就是卡特拉数了，代码这里就不贴出了，求赞 QwQ。