T4 题解

wrzSama · 2022-10-11 21:22:00 · 个人记录

首先，我们发现 wrzSama 和 WHY2022 中一定会有 1 人坐在最高的座位上，可以考虑依次判断另一个人坐在其他座位上行不行。考虑另一人坐在最高座位的右边（坐在左边的情况把序列反转再考虑一遍），整个序列就被分成了 3 段：

第 1 段为从座位 1 到最高座位：包括 2 递增的序列。

第 2 段为从最高座位到另一人坐的座位：包括 1 个递增的序列和 1 个递减的序列，递减的序列以最高座位为开头，递增的序列以另一人坐的座位为结尾。

第 3 段为从另一人坐的座位到座位 n：包括 2 个递减的序列。

为了让拆分尽量可行，我们要贪心地让第 1 段中不以最高座位结尾的递增序列的末尾尽量小，第 3 段中不以另一人的座位为开头的递减序列的开头尽量小。

我们可以对于这 2 段 dp 一下，f1_{i} 表示将前 i 个座位分成 2 个递增序列后不以座位 i 结尾的递增序列的结尾的最小值，f2_i 表示将后 n-i+1 个座位分成 2 个递减序列后不以座位 i 为开头的递减序列的开头的最小值。

我们可以直接将 f_2 的值计算到最高座位的位置，然后从最高座位到座位 n 依次判断可行性。对于第 2 段，我们可以再进行一下 dp，dp_{i,0} 表示把座位 i 放在递增序列末尾递减序列末尾的最大值，dp_{i,1} 表示把座位 i 放在递减序列末尾递增序列末尾的最小值。dp 的初值可以从第 1 段计算的 f1 转移过来。

于是，对于位置 i ，我们直接通过判断 dp_{i,0} 是否大于 f2_i 来判断另一个人能否坐在位置 i。当然，最后还要将求出的答案乘以 2，因为 wrzSama 和 WHY2022 可以互相交换座位。时间复杂度 O(n)，可以通过本题。