逢低吸纳

形式化题目

给定一个长度为 $N$ 的正整数序列 $A = [a_1, a_2, \dots, a_N]$ 。

求：

序列 $A$ 的最长严格下降子序列（Strictly Decreasing Subsequence）的长度 $L$ 。
长度达到 $L$ 的严格下降子序列的方案数。其中，两个方案被视为相同当且仅当它们所包含的数值序列完全相同。需要输出去重后的方案数。

正解

思路

1. 问题拆解与长度计算

若不考虑去重，求最长严格下降子序列（LDS）是经典动态规划：

设 $f[i]$ 表示以第 $i$ 个数 $a_i$ 结尾的最长严格下降子序列长度。
状态转移为：
$f[i] = 1 + \max(\{0\} \cup \{f[j] \mid 1 \leqslant j < i \land a_j > a_i\})$

2. 去重方案数计数的关键观察

难点在于第二问：如果两个方案构成的数值序列相同，只能计算一次。

例如，对于下标 $j_1 < j_2 < i$ ，若有 $a_{j_1} = a_{j_2}$ 且 $f[j_1] = f[j_2] = f[i] - 1$ ：

以 $a_{j_1}$ 结尾的合法子序列的形式为 $(\dots, a_{j_1})$ ，以 $a_{j_2}$ 结尾的形式为 $(\dots, a_{j_2})$ 。因为 $a_{j_1} = a_{j_2}$ ，它们作为前驱拼接到 $a_i$ 之后时，倒数第二个数字的数值完全相同。
由于 $j_1 < j_2$ ，任何能在 $j_1$ 前面接上的合法前驱，其下标必然也位于 $j_2$ 之前。因此以 $j_2$ 为结尾的不同下降子序列集合，完整包含了以 $j_1$ 为结尾的集合。
如果同时从 $j_1$ 和 $j_2$ 转移至 $i$ ，就会产生重复的数值子序列。

核心去重策略：对于相同的前驱数值 $v$ ，在转移给 $i$ 时，只需要保留最靠后（即下标最大）的那一个前驱位置，将其方案数计入；更靠前的相同数值前驱必须忽略。

具体操作：

当确定了 $f[i]$ 后，前驱必须满足 $f[j] = f[i] - 1$ 且 $a_j > a_i$ 。
我们让 $j$ 从 $i - 1$ 开始倒序遍历到 $1$ 。
用一个集合（或标记数组）记录已经访问过的前驱数值。
当首次遇到数值为 $a_j$ 的前驱时，将其方案数累加至当前位置，并记录该数值已访问；之后再遇到相同的数值则直接跳过。

3. 哨兵技巧简化全序列统计

在原序列最后添加一个极小值元素 $a_{N+1} = 0$ （由于题目股价均为正整数， $0$ 严格小于所有输入股价）：

以 $a_{N+1}$ 结尾的最长下降子序列必然汇集了前面所有的最长序列。
其长度恰好为 $L + 1$ ，去重后的方案数恰好为全序列的最终方案数。
这样只需一套统一的双层循环逻辑，免去最后对全序列结尾元素的单独去重统计。

状态推导与图示

以样例 $A = [68, 69, 54, 64, 68, 64, 70, 67, 78, 62, 98, 87]$ 为例，末尾追加哨兵 $0$ ：

下标 $i$	1	2	3	4	5	6	7	8	9	10	11	12	13(哨兵)
股价 $a_i$	68	69	54	64	68	64	70	67	78	62	98	87	0
最长长度 $f[i]$	1	1	2	2	2	3	1	3	1	4	1	2	5
去重方案数 $g[i]$	1	1	2	2	1	1	1	1	1	2	1	1	2

在上表中：

当计算第 6 天（股价 64， $f[6]=3$ ）时，前驱目标长度为 2。可供转移的位置有第 4 天（股价 64）和第 5 天（股价 68），前驱数值不同，均被计入。
当计算第 10 天（股价 62， $f[10]=4$ ）时，前驱目标长度为 3，合格前驱有第 6 天（股价 64）和第 8 天（股价 67），累加方案数 $1 + 1 = 2$ 。
最终哨兵节点 $a_{13}=0$ 的 $f[13] = 5$ ，对应的去重方案数为 $g[13] = 2$ 。还原实际结果为：最长长度 $5 - 1 = 4$ ，总方案数 $2$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 06:11
# update_at: 2026-10-01 06:11

import sys


def find_lds_with_unique_ways(prices: list[int]) -> tuple[int, int]:
    """计算最长严格下降子序列的长度以及数值去重后的最长方案数。"""
    # 追加 0 作为末尾哨兵，汇聚所有最长下降子序列终点
    extended = prices + [0]
    total_len = len(extended)
    lengths = [1] * total_len
    ways = [1] * total_len

    for i in range(total_len):
        cur_price = extended[i]
        best_len = 1
        for j in range(i):
            if extended[j] > cur_price and lengths[j] + 1 > best_len:
                best_len = lengths[j] + 1
        lengths[i] = best_len

        if best_len == 1:
            ways[i] = 1
        else:
            total_ways = 0
            visited: set[int] = set()
            target_len = best_len - 1
            # 倒序遍历取同数值的最靠后位置，避免前驱数值相同的子序列重复累加
            for j in range(i - 1, -1, -1):
                prev_price = extended[j]
                if prev_price > cur_price and lengths[j] == target_len and prev_price not in visited:
                    visited.add(prev_price)
                    total_ways += ways[j]
            ways[i] = total_ways

    return lengths[-1] - 1, ways[-1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    prices = [next(data) for _ in range(n)]

    max_len, total_schemes = find_lds_with_unique_ways(prices)
    print(f"{max_len} {total_schemes}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:13
 * update_at: 2026-10-06 11:13
 */

#include <cstdio>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

const int MAXN = 5005;       // N 最大 5000，再加末尾哨兵
const int BASE = 1000000000; // 大整数压 9 位十进制，方案数可能超过 64 位

// 非负大整数，digits 低位在前，digits[0] 存放最低 9 位
struct BigInt {
    vector<int> digits;
};

ll a[MAXN];     // a[i] 为第 i 天股价，a[n+1] 是补上的哨兵 0
ll f[MAXN];     // f[i] 为以第 i 天结尾的最长严格下降子序列长度
BigInt g[MAXN]; // g[i] 为以第 i 天结尾且长度取到 f[i] 的去重方案数

// 大整数加法：x += y
void big_add(BigInt &x, const BigInt &y) {
    int carry = 0;
    for (int i = 0; i < (int)y.digits.size() || carry > 0; i++) {
        if (i == (int)x.digits.size()) {
            x.digits.push_back(0);
        }
        ll cur = x.digits[i] + carry;
        if (i < (int)y.digits.size()) {
            cur += y.digits[i];
        }
        x.digits[i] = cur % BASE;
        carry = cur / BASE;
    }
}

// 输出大整数，最高位不带前导零，其余每组补足 9 位
void big_print(const BigInt &x) {
    if (x.digits.empty()) {
        printf("0");
        return;
    }
    printf("%d", x.digits.back());
    for (int i = (int)x.digits.size() - 2; i >= 0; i--) {
        printf("%09d", x.digits[i]);
    }
}

int main() {
    ll n;
    if (scanf("%lld", &n) != 1) {
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    a[n + 1] = 0; // 哨兵：0 比所有正整数股价都小，汇聚全部最长下降子序列
    int total = n + 1;

    for (int i = 1; i <= total; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] > a[i] && f[j] + 1 > f[i]) {
                f[i] = f[j] + 1;
            }
        }

        if (f[i] == 1) {
            g[i].digits.clear();
            g[i].digits.push_back(1);
            continue;
        }

        // 从后往前找长度恰为 f[i]-1 的前驱；同数值只取最靠后的位置，避免数值序列重复
        g[i].digits.clear();
        set<ll> seen;
        for (int j = i - 1; j >= 1; j--) {
            if (a[j] > a[i] && f[j] == f[i] - 1 && seen.find(a[j]) == seen.end()) {
                seen.insert(a[j]);
                big_add(g[i], g[j]);
            }
        }
    }

    printf("%lld ", f[total] - 1);
    big_print(g[total]);
    printf("\n");
    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(N^2)$ 。外层循环遍历 $N+1$ 个位置，内层在找最大长度与倒序求和时各遍历最多 $i$ 次。单次哈希集合插入与查找平均为 $\mathcal{O}(1)$ 。在 $N \leqslant 5000$ 下总运算次数约为 $1.25 \times 10^7$ ，运行时间约为 0.5s，完全在时限之内。
空间复杂度： $\mathcal{O}(N)$ 。用于存储数组及局部去重哈希集合。

总结

数值去重 vs 下标去重：本题的关键在于识别到相同的数值前驱在不同位置产生的信息包含关系，通过“优先选择靠后下标”这一贪心性质，完美转化了复杂的去重子集计算。
末尾哨兵统一收敛：通过在序列末尾补 $0$ ，把寻找全局最大值及其去重统计的问题直接归约到单点的转移过程中，保证了代码实现的简洁与严谨。

目录

形式化题目

正解

思路

1. 问题拆解与长度计算

2. 去重方案数计数的关键观察

3. 哨兵技巧简化全序列统计

状态推导与图示

代码

复杂度

总结