题解

思路

任意双调排列的峰值必然是 $n$。选定峰值左侧出现的值集合 $L\subseteq\{1,\ldots,n-1\}$ 后，排列被唯一确定：$L$ 升序、然后是 $n$、剩余元素降序。双调峰值不得在两端，所以 $1\le |L|\le n-2$。

设 $c_v=|L\cap[1,v]|$。值 $v<n$ 在排列中的位置为

$$pos(v)=\begin{cases}c_v,&v\in L,\\1+n-v+c_v,&v\notin L.\end{cases}$$

而 $pos(n)=|L|+1$。

做法

子任务 1 枚举 $1\ldots n$ 的全排列，检查双调性与两个固定位置。

子任务 2 枚举 $L$ 的所有子集，按上式计算 $x,y$ 的位置。

满分做法枚举 $x$ 和 $y$（若小于 $n$）是否属于 $L$。固定归属后，上式直接给出处理到 $x$ 或 $y$ 时已选元素数的要求。按数值从 $1$ 到 $n-1$ 做选/不选 DP，在两个检查点只保留所需选取数的状态。最后若 $x=n$ 或 $y=n$，再检查 $|L|+1$ 是否等于相应位置。

复杂度

满分算法时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。