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

chengyifan91 · 2026-03-11 16:04:24 · 题解

首先，n\le 50 做法太没有前途了，因此我们可以想想 O(n^3)。

我们可以转换一下，一段 (l_i,r_i) 只需要满足：

• 存在一个 k 使得 l_i\sim k 是严格单调递增，k\sim r_i 是严格单调递减；

就是合法的。

不妨令 t=\sum\limits_{j=l_i+1}^{r_i}[a_{j-1}<a_j]-\sum\limits_{j=l_i+1}^{r_i}[a_{j-1}>a_j]，则第二个条件相当于 t=0。

设 dp_{i,j,k} 表示以 i 为结尾，当前 t=j，k 代表当前是上升状态还是下降状态（上升为 0，下降为 1）的最长子序列长度，则有以下转移：

• 若 a_k<a_i，则 k 前面也要保证单调递增，因此只能从上升状态转移，即 dp_{i,j,0}=\max(dp_{k,j-1,0})+1 (k<i,a_k<a_i)。
• 若 a_k>a_i，则 k 前面可以单调递增也可以先递增再递减，上升和下降都可以转移过来，即 dp_{i,j,1}=\max(dp_{k,j+1,0},dp_{k,j+1,1})+1 (k<i,a_k>a_i)。

考虑初始化：a_i 可以是一个子序列的开头，即 dp_{i,0,0}=1。

:::info[暴力代码]

#include<bits/stdc++.h>
using namespace std;

const int N = 2010;
int dp[N][N][2], a[N];

int main() {
    memset(dp, -0x3f, sizeof(dp));
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        dp[i][0][0] = 1; 
        for (int j = 0; j <= i; j++) {
            for (int k = 1; k < i; k++) {
                if (j && a[k] < a[i]) dp[i][j][0] = max(dp[k][j-1][0]+1, dp[i][j][0]);
                if (a[k] > a[i]) dp[i][j][1] = max({dp[k][j+1][0]+1, dp[k][j+1][1]+1, dp[i][j][1]});
                dp[i][0][0] = max(dp[i][0][0], dp[k][0][1]+1);
            }
        }
        ans = max(ans, dp[i][0][1]);
    }
    cout << ans;
    return 0;
}

:::

考虑优化，注意到 \max(dp_{k,j-1,0}) (k<i,a_k<a_i) 是可以用树状数组维护的（需要离散化），我们开 n 棵树状数组即可。\max(dp_{k,j+1,0},dp_{k,j+1,1}) (k<i,a_k>a_i) 也是同理，只不过是反向的。