最长不下降子序列（LNDS 长度 + 方案数）

题目解析

题意

多组数据，每组给定一个序列，求最长不下降子序列（LNDS）的长度，以及达到该长度的方案数。

思路

经典 LIS 的 DP 扩展，多维护一个方案数即可。

设：

$dp[i]$ ：以 $i$ 结尾的最长上升子序列长度
$cnt[i]$ ：达到 $dp[i]$ 长度的方案数

转移：

初始化： $dp[i] = 1,\; cnt[i] = 1$ （每个元素自身）
对 $j < i$ ，若 $a[j] < a[i]$ ：
- $dp[j] + 1 > dp[i]$ ：更新 $dp[i]$ ， $cnt[i] = cnt[j]$
- $dp[j] + 1 = dp[i]$ ： $cnt[i] += cnt[j]$

最后取 $\max dp[i]$ 为 LIS 长度，累加所有 $dp[i] = \text{max\_len}$ 的 $cnt[i]$ 为方案数。

复杂度

$O(T \cdot n^2)$ ， $n \le 2000$ 时可接受。

代码

cpp

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

const int N = 2005;
int a[N];
int dp[N];   // dp[i]: 以 i 结尾的最长不下降子序列长度
long long cnt[N]; // cnt[i]: 达到 dp[i] 长度的方案数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            dp[i] = 1;   // 每个元素自身构成长度为 1 的子序列
            cnt[i] = 1;  // 方案数为 1
        }

        int max_len = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] <= a[i]) { // 非递减
                    if (dp[j] + 1 > dp[i]) {
                        // 找到了更长的子序列，更新长度和方案数
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        // 同样长度的子序列，累加方案数
                        cnt[i] += cnt[j];
                    }
                }
            }
            max_len = max(max_len, dp[i]);
        }

        // 统计所有达到最长长度的方案数
        long long total = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == max_len) {
                total += cnt[i];
            }
        }

        cout << max_len << " " << total << "\n";
    }

    return 0;
}

最长不下降子序列（LNDS 长度 + 方案数）

目录

题目解析

题意

思路

复杂度

代码