题解：P15442 [蓝桥杯 2025 国研究生组] 山峰子序列

· · 题解

这不就是给最长上升子序列板子题套了个壳就搬过来了吗？

子序列问题我们一般的状态设计第一维都是子序列结尾的位置。

第二维我们可以考虑这个子序列有上升和下降两种走向，直接设 0/1 状态。

第三维，我们发现同一组上升和下降的子序列长度是相同的，于是第三维我们直接来维护上升和下降的长度。

设第三维记录的长度为 s，上升一次会使 s 加 1，下降一次会使 s 减一，s 不能为负数，且只有 s=0 时才能从下降转到上升。

dp 数组的值就设为长度喽。

此时如下 4 种转移：

  1. 扩展上升段，dp_{i,0,j}=\max_{0\le k<i,a_k<a_i} dp_{k,0,j-1}+1。

  2. 扩展下降段，dp_{i,1,j}=\max_{0\le k<i,a_k>a_i} dp_{k,1,j+1}+1。

  3. 上升转下降，dp_{i,1,j}=dp_{i,0,j}。

  4. 下降转上升，dp_{i,0,0}=dp_{i,1,0}。

这就可以 O(n^3) 解出这道题了。

接着考虑优化，发现第 3 种和第 4 种转移是 O(1) 转移的，所以我们只用去管前两种。

前两种是什么经典问题啊，二维偏序的 dp 啊。

此时你发现 i 是从小到大枚举的，转移中 0\le k<i 可以自动满足。

所以为何满足 a_k 与 a_j 的大小关系，直接考虑在值域上维护数据结构，也就是需要一个能动态插入，查询前缀最小值和后缀最小值的数据结构。

可以直接树状数组，查询后缀的话你就把 a_i 变成 10^6-a_i 就行了。

值域是 10^6 的，我们无法开 O(n) 个值域树状数组，所以我们直接离散化，将值域降到了 O(n)。

时间复杂度 O(n^2\log n)，可以过题。

解法全都喂给你了，自己去写代码吧。