详解“跌宕起伏的事件序列”问题：动态规划+区间转移的计数技巧

用户11944663

发布于 2025-12-22 11:10:07

1080

详解“跌宕起伏的事件序列”问题：动态规划+区间转移的计数技巧

在编程竞赛中，计数类动态规划常结合“状态转移+区间扩展”的思路，解决序列构造的方案数问题。本文以“事件序列的跌宕起伏排列”为例，拆解这类问题的分析逻辑、实现步骤与代码细节。

一、问题重述：什么是“跌宕起伏的序列”？

给定 n 个事件（每个事件有类型 a_i），要求构造序列 B，满足：序列的每个前缀的最后一个元素，都是该前缀的最大值或最小值。统计本质不同的序列 B 的数量（对 998244353 取模）。

二、核心思路：区间DP+计数统计

要满足“每个前缀的最后一个元素是当前前缀的最值”，序列的构造过程必然是逐步扩展最值区间：

初始时，序列只有一个元素（既是最大值也是最小值）；
每一步新增的元素，必须是当前序列的新最大值或新最小值（否则无法满足前缀的最值要求）。

基于此，我们可以用区间动态规划来建模：

先对原数组去重并排序，得到有序的唯一元素列表（记为 s[0..m-1]，m 是去重后的元素个数）；
统计每个唯一元素的出现次数 cnt[i]（即原数组中 s[i] 出现了多少次）；
定义 dp[i][j]：表示当前序列的最小值是 s[i]、最大值是 s[j] 时，合法序列的数量。

三、具体实现步骤

步骤1：预处理（排序+去重+计数）

首先对原数组排序，再去重得到有序的唯一元素列表，同时统计每个元素的出现次数：

// 排序原数组
qsort(a, n, sizeof(int), cmp);
// 去重并统计每个元素的出现次数
int m = unique(a, n); // 去重后的元素个数
int *cnt = (int *)malloc(m * sizeof(int));
cnt[0] = 1;
int idx = 0;
for (int i = 1; i < n; i++) {
    if (a[i] == a[idx]) cnt[idx]++;
    else {
        idx++;
        cnt[idx] = 1;
    }
}

步骤2：DP初始化

当序列只包含一个元素时（即区间 [i,i]），方案数等于该元素的出现次数（每个相同元素都是一种选择）：

long long **dp = (long long **)malloc(m * sizeof(long long *));
for (int i = 0; i < m; i++) {
    dp[i] = (long long *)calloc(m, sizeof(long long));
    dp[i][i] = cnt[i]; // 单个元素的方案数是其出现次数
}

步骤3：区间DP转移（按区间长度扩展）

我们按区间长度从小到大处理，确保转移时子问题已求解：

若当前区间是 [i,j]，它只能由两种方式扩展而来：
1. 扩展最大值：从区间 [i,j-1]（最小值 s[i]，最大值 s[j-1]）扩展到 [i,j]，新增的 s[j] 是新最大值，方案数为 dp[i][j-1] * cnt[j]（cnt[j] 是 s[j] 的可选数量）；
2. 扩展最小值：从区间 [i+1,j]（最小值 s[i+1]，最大值 s[j]）扩展到 [i,j]，新增的 s[i] 是新最小值，方案数为 dp[i+1][j] * cnt[i]（cnt[i] 是 s[i] 的可选数量）。

转移代码如下：

for (int len = 2; len <= m; len++) { // 区间长度从2到m
    for (int i = 0; i + len - 1 < m; i++) {
        int j = i + len - 1;
        // 扩展最大值到j
        dp[i][j] = (dp[i][j] + dp[i][j-1] * cnt[j]) % MOD;
        // 扩展最小值到i
        dp[i][j] = (dp[i][j] + dp[i+1][j] * cnt[i]) % MOD;
    }
}

步骤4：输出结果

最终答案是覆盖所有唯一元素的区间 [0, m-1] 对应的方案数：

printf("%lld\n", dp[0][m-1] % MOD);

四、完整代码与解释

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 998244353

// 排序比较函数
int cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// 去重函数，返回去重后的元素个数
int unique(int *arr, int n) {
    if (n == 0) return 0;
    int idx = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[idx-1]) {
            arr[idx++] = arr[i];
        }
    }
    return idx;
}

int main() {
    int n;
    scanf("%d", &n);
    int *a = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // 步骤1：排序、去重、统计出现次数
    qsort(a, n, sizeof(int), cmp);
    int m = unique(a, n);
    int *cnt = (int *)malloc(m * sizeof(int));
    cnt[0] = 1;
    int idx = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] == a[idx]) cnt[idx]++;
        else {
            idx++;
            cnt[idx] = 1;
        }
    }

    // 步骤2：初始化DP数组
    long long **dp = (long long **)malloc(m * sizeof(long long *));
    for (int i = 0; i < m; i++) {
        dp[i] = (long long *)calloc(m, sizeof(long long));
        dp[i][i] = cnt[i];
    }

    // 步骤3：区间DP转移
    for (int len = 2; len <= m; len++) {
        for (int i = 0; i + len - 1 < m; i++) {
            int j = i + len - 1;
            // 扩展最大值
            dp[i][j] = (dp[i][j] + dp[i][j-1] * cnt[j]) % MOD;
            // 扩展最小值
            dp[i][j] = (dp[i][j] + dp[i+1][j] * cnt[i]) % MOD;
        }
    }

    // 步骤4：输出结果
    printf("%lld\n", dp[0][m-1] % MOD);

    // 释放内存
    free(a);
    free(cnt);
    for (int i = 0; i < m; i++) {
        free(dp[i]);
    }
    free(dp);

    return 0;
}

五、复杂度分析

时间复杂度：( O(n \log n + m^2) )
- 排序耗时 ( O(n \log n) )；
- 区间DP转移耗时 ( O(m^2) )（( m ) 是去重后的元素个数，( m \leq n )）。
空间复杂度：( O(n + m^2) )
- 存储原数组、计数数组的空间是 ( O(n) )；
- DP二维数组的空间是 ( O(m^2) )。