LGR199D(P11079) 题解

Register_int · 2024-09-22 16:29:08 · 题解

先对 a 离散化。思路当然是 dp_{i,j} 算以 i 结尾最高峰为 j 的子序列有多少个。但是有些问题：

• 每个山峰至少要有一个上坡。
• 若出现了 V 字形的峡谷，那么同一个子序列会对应两种划分成山峦的方案。

解决方法是添加一个起始点来区分。设 dp_{i,j,0/1/2/3} 表示以 i 结尾，最高峰为 j，当前刚开始上坡/正在上坡/刚开始下坡/正在下坡的方案数，那么答案为 \sum dp_{i,j,2}+dp_{i,j,3}。考虑转移：

转移需要枚举上一个，复杂度为 O(n)，总时间复杂度为 O(n^3)。发现转移时对于同个 j 求的是所有 <a_i 或 >a_i 的位置之和，可以用树状数组优化到 O(n^2\log n)。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e2 + 10;
const int mod = 998244353;

inline void add(int &x, int y) { x += y, x < mod || (x -= mod); }

int n, m, a[MAXN], b[MAXN], dp[MAXN][MAXN][4], ans;

// dp_i,j,0:新开一个向上单点（只能从下坡转移） 
// dp_i,j,1:上坡
// dp_i,j,2:新开一个向下单点 
// dp_i,j,3:下坡 

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1), m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    for (int i = 1; i <= n; i++) {
        dp[i][0][0] = 1;
        for (int j = 1; j < i; j++) {
            for (int k = 0; k <= m; k++) {
                add(dp[i][k][0], dp[j][k][2]);
                if (a[i] <= a[j]) add(dp[i][k][0], dp[j][k][3]);
            }
        }
        for (int j = 1; j < i; j++) {
            if (a[j] >= a[i]) continue;
            for (int k = 0; k <= m; k++) {
                add(dp[i][k][1], dp[j][k][0]);
                add(dp[i][k][1], dp[j][k][1]);
            }
        }
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i]) continue;
            for (int k = 0; k < a[j]; k++) {
                add(dp[i][a[j]][2], dp[j][k][1]);
            }
        }
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i]) continue;
            for (int k = 0; k <= m; k++) {
                add(dp[i][k][3], dp[j][k][2]);
                add(dp[i][k][3], dp[j][k][3]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            add(ans, dp[i][j][2]);
            add(ans, dp[i][j][3]);
        }
    }
    printf("%d", ans);
}