Catalan 相关问题-CF1924D题解

· · 题解

题目传送门

看到题干知道是 \text{Catalan} 数的很经典的 \text{Dyck} 路径问题变体。

比较容易想到的是传统的画法：一个 n\times m 网格，将括号序列对应到一条从 (0,0) 到 (n,m) 的路径，是 \texttt( 则往右走，是 \texttt) 则往左走。但我更喜欢的表达：一个赌徒在赌场赌钱，\texttt( 代表赢钱，\texttt) 代表输钱，左边 (t,q) 表示 t 时刻赌徒有 q 元钱，则最后对应从 (0,0) 到 (n+m,n-m) 的折线路径。以下使用此组合模型对问题进行叙述。

下面关键在于如何对最长子序列为 k 进行刻画：注意到赌徒赢钱次数一定是越多越好，最后有剩余的只需去掉最后几个即可。而要 k 尽可能大，序列中包含尽可能多的输钱的情形。这样，贪婪算法的想法就产生了：遇到赢钱全部保留，遇到输钱，若输完钱数非负，则加入序列，否则跳过。不难验证此算法是最优的。

在此算法下，序列长度为 2k 代表输了 k 次钱，因此有 m-k 次输钱没用上。但这些时刻位置比较明确，如下图所示：

第一次未用上代表此时已经输光，即触碰到 x 轴，我们将轴向下平移一个单位。第二次未用上即为第一次触碰到变换后的实轴，再将其向下平移一个单位。共 m-k 次，因此最终平移 m-k 个单位，为直线 y=k-m。

现在只需计算折线最低点恰在 y=k-m 上的方法数了，运用经典的 \text{Dyck} 路径对应方法可以解决。对任何一条 y=t，设 N(t) 为最低点不高于 y=t 的方法数，则将每一条路径与 y=t 的最后一个交点取出，将之后的路径关于 y=t 对称，这样构造了一个从 (0,0) 到 (n+m,2t-n+m) 的任意路径的双射（双射细节的证明读者自行验证）。从而 N(t)=\binom{n+m}{t+m}。最后，所求即为 N(k-m)-N(k-m-1)=\binom{n+m}{k}-\binom{n+m}{k-1}，求出表达式后就基本做完了。

希望这次能过了