形式化题目

给定长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$。称下标序列 $i_1 < i_2 < \dots < i_k$ 是不下降子序列，如果

记 $L$ 为所有不下降子序列长度的最大值。要求在所有长度为 $L$ 的不下降子序列中，取出值序列 $(a_{i_1}, \dots, a_{i_L})$ 字典序最小的那一条。

注意比较的是值序列而不是下标序列。样例 1 的序列是 10 11 12 13 1 2 3 4，两条长度 4 的链分别为 10 11 12 13 与 1 2 3 4，答案是后者。$n \leqslant 300$，元素可重复。

正解

思路

朴素做法不行。 最直接的想法是枚举全部 $2^n$ 个子序列，逐个检查是否不下降，在长度最大的那些里挑字典序最小的。$n = 300$ 时 $2^{300} \approx 2 \times 10^{90}$，瓶颈不在"检查"而在于把"选了哪些位置"当成了状态，状态数本身就是指数级。

先拆目标。 题目其实问了两个问题：最长有多长（唯一答案 $L$），以及在这个长度下值序列的字典序最小是多少。这两件事必须按顺序做。样例 1 里 10 11 12 13 与 1 2 3 4 长度都是 4，后者字典序更小，所以答案是后者；而这里能直接比较的前提是已经知道 $L = 4$——如果连长度都没定，连"当前还差几个元素"都说不清，更没法判断某个选择之后还能不能凑满。所以第一步只求 $L$，第二步再在长度恰好为 $L$ 的前提下逐位比字典序。

把 LIS 的方向翻过来。 常见的 LIS 状态是"以 $a_i$ 结尾的最长长度"，转移看左边。但本题要先定长度、再从左往右逐位构造答案链，需要知道的是"从某个位置出发还能往下走多远"；"以 $a_i$ 结尾"回答的是相反方向的问题，用不上。于是把状态翻过来，定义

右边取不到元素时 $g_i = 1$（$a_i$ 自己成链）。倒着枚举 $i$，用到的 $g_j$ 就都已算好。

$g_i$ 不只是长度，它还是一个潜力值：从 $i$ 出发还能往下延伸多少。这一点正是构造字典序最小方案的关键。

用潜力值刻画"能不能补齐"。 假设已经选好了链的末尾（值为 $v$、下标为 $p$），还差 $c$ 个元素。现在想选下标 $j$ 作为下一个元素，它合法吗？

• 不下降要求 $j > p$ 且 $a_j \geqslant v$；
• 更关键的是 $g_j \geqslant c$：选 $j$ 之后最多还能接 $g_j$ 个元素，而后面还需要 $c$ 个（$j$ 本身算一个），所以 $g_j$ 必须够长。

反过来，只要 $g_j \geqslant c$，因为从 $j$ 出发确实存在一条长度为 $g_j$ 的不下降链，取它的前 $c$ 个就能把后面填满。于是"可行性"被两个不等式精确刻画：

这就是第一步必须先用 DP 求出 $g$ 的原因：没有 $g$，判断"选了它之后还能不能凑够 $L$"就只能再跑一次搜索。

逐位贪心。 既然每一步的可行集都算得出来，字典序最小就顺理成章：维护（起点 start = 上一个选中下标 $+1$、下界 lower = 已选末尾值、还差 need 个），每一步在

中选 $a_j$ 最小的那个，然后 start = j + 1、lower = a_j、need -= 1，重复 $L$ 次。

为什么这样得到的是字典序最小？对已选位置数 $i$ 归纳，维护两件事：贪心的前 $i$ 项一定能补成某个最优解；且对任意"前 $i$ 项取值与贪心相同"的最优解 $S$，贪心第 $i$ 项用的下标不大于 $S$ 的。

归纳时取这样一个 $S$。记贪心已选末尾下标为 $p_G$、$S$ 已选末尾下标为 $p_S$，归纳假设给出 $p_G \leqslant p_S$。$S$ 要选的下一个元素下标 $j_S$ 满足 $j_S > p_S \geqslant p_G$、$a_{j_S} \geqslant s_i = u_i$、且从 $j_S$ 出发还能再走 $L - i$ 步（因为 $S$ 本身就走到了），也就是 $g_{j_S} \geqslant L - i$。三条全中，$j_S$ 落在贪心这一步的候选集里，所以贪心选出的值 $u_{i+1} \leqslant s_{i+1}$。若取等号，贪心在该值的所有候选中取最靠前的下标（min 在键并列时保留最先出现的元素），于是 $p_G' \leqslant p_S'$ 继续成立；下标更靠前只会让后续候选集更大，归纳不会断。

归纳到头，对任意最优解 $S$，设 $t$ 是第一个取值不同的位置：前面 $t-1$ 项相同，上面这一步给出 $u_t \leqslant s_t$，而 $t$ 是首个不同位置故不取等号，于是 $u_t < s_t$。$S$ 任意，所以贪心输出的字典序最小。

注意比较键必须是值而不是下标：样例 3 中第一步下标 1（值 2）与下标 4（值 1）都满足 $g \geqslant 3$，必须取后者，答案才是 1 4 6。

用样例 3 走一遍。 序列 $a = (2, 6, 8, 1, 5, 7, 4, 6)$，$n = 8$。

先倒序（从右往左）算 DP。表中"可接下标"是满足 $j > i$ 且 $a_j \geqslant a_i$ 的全部位置：

从右往左读这张表。$i = 8$ 右边没有元素，$g_8 = 1$。$i = 7$（值 4）右边只有 $a_8 = 6 \geqslant 4$，故 $g_7 = 1 + g_8 = 2$。$i = 5$（值 5）的右边是 $7, 4, 6$，其中 $a_6 = 7 \geqslant 5$、$a_8 = 6 \geqslant 5$ 而 $a_7 = 4 < 5$ 不合法，于是 $g_5 = 1 + \max(g_6, g_8) = 1 + 1 = 2$。

$i = 1$（值 2）时最容易看错：第三行的可接集合是 $\{2,3,5,6,7,8\}$，不包含下标 4，虽然 $4 > 1$ 但 $a_4 = 1 < a_1 = 2$，接不上；在这六个位置里 $g$ 的最大值是 2，所以 $g_1 = 1 + 2 = 3$。读表时第二行（值）和第三行（下标）必须一起看，两者同时成立才是合法前驱。最终 $L = \max g = 3$。

再逐位贪心，初值 start = 1、lower = 无、need = 3：

第一步两个候选的 $g$ 都不小于 3（$g_1 = 3$、$g_4 = 3$），取值更小的 1；这一步之后 need 变成 2，起点挪到 5、下界变成 1。第二步候选是下标 5（值 5，$g_5 = 2$）与下标 7（值 4，$g_7 = 2$），选值更小的 4；若在第一步贪心地取了更靠前的下标 1，链条会变成 2 4 6，字典序更大。第三步只剩下标 8 可选，得 1 4 6，与样例输出一致。

代码

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#!/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 01:50
# update_at: 2026-10-01 02:01

import sys


def suffix_lengths(seq: list[int]) -> list[int]:
    """g[i] = 以 seq[i] 开头的最长不下降子序列长度 = 1 + max{g[j] : j > i 且 seq[j] >= seq[i]}。"""
    g = [1] * len(seq)
    for i in range(len(seq) - 1, -1, -1):  # 倒着算，用到的 g[j] 都已就绪
        g[i] = 1 + max((g[j] for j in range(i + 1, len(seq)) if seq[j] >= seq[i]), default=0)
    return g


def lex_smallest(seq: list[int], g: list[int]) -> list[int]:
    """在全部最长不下降子序列中挑出字典序最小的那一条。

    每一步在候选下标里取值最小的元素：候选 = 下标在当前之后、值不小于已选末尾、
    且以它开头的 g 值还够长（g[j] >= 剩余个数）。够长保证后面一定能补齐，
    取最小保证本位最小；并列时 min 保留最靠前的下标，留给后面的选择最多。
    """
    picked: list[int] = []
    start = 0                      # 下一个元素只能从 start 及之后取
    lower: int | None = None       # 已选末尾的值；None 表示还没选过，不受下界限制
    need = max(g)                  # 还差几个元素才够最长
    while need:
        j = min(
            (j for j in range(start, len(seq))
             if g[j] >= need and (lower is None or seq[j] >= lower)),
            key=seq.__getitem__,
        )
        picked.append(seq[j])
        start, lower, need = j + 1, seq[j], need - 1
    return picked


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 题面的序列长度
    seq = [next(data) for _ in range(n)]

    g = suffix_lengths(seq)
    ans = lex_smallest(seq, g)
    print(len(ans))
    print(*ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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 01:45
 * update_at: 2026-10-06 01:45
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 305;

ll a[MAXN];  // 输入序列，下标从 1 开始
ll g[MAXN];  // g[i] = 以 a[i] 开头的最长不下降子序列长度（潜力值：从 i 出发还能延伸多远）
ll ans[MAXN]; // 答案序列（按顺序保存选出的值）
ll n;        // 序列长度

// 阶段 1：倒序 DP 求 g[i] = 1 + max{ g[j] : j > i 且 a[j] >= a[i] }
// 倒着枚举 i，用到的 g[j] 都已算好
void solve_dp() {
    for (ll i = n; i >= 1; --i) {
        g[i] = 1; // 右边接不上任何元素时，a[i] 自己成链
        for (ll j = i + 1; j <= n; ++j)
            if (a[j] >= a[i] && g[j] + 1 > g[i])
                g[i] = g[j] + 1;
    }
}

// 阶段 2：逐位贪心构造字典序最小的最长不下降子序列
// 每一步在 { j > 上一个选中下标 : g[j] >= 还差个数 且 a[j] >= 已选末尾值 }
// 中取 a[j] 最小者；g[j] >= need 用潜力值保证后面一定补得满，
// 值并列时取最靠前的下标，留给后面的选择最多。
void solve_greedy() {
    ll need = 0;    // 还差几个元素才够最长
    for (ll i = 1; i <= n; ++i)
        if (g[i] > need)
            need = g[i]; // need 初值 = 最长长度 L = max g[i]

    ll start = 1;   // 下一个元素只能从 start 及之后取
    ll lower = 0;   // 已选末尾的值；还没选时不设下界（见 lower_used）
    bool lower_used = false;

    ll cnt = 0;     // 已选个数
    while (need > 0) {
        ll best = 0; // 选中的下标，0 表示这一步还没找到候选
        for (ll j = start; j <= n; ++j) {
            if (g[j] < need)          continue;  // 潜力不够，后面凑不满
            if (lower_used && a[j] < lower) continue; // 不满足不下降
            // 比较“值”而不是下标；值并列取最靠前的 j（先遇到的不被覆盖）
            if (best == 0 || a[j] < a[best])
                best = j;
        }
        cnt = cnt + 1;
        ans[cnt] = a[best];
        start = best + 1; // 下标严格递增
        lower = a[best];
        lower_used = true;
        need = need - 1;
    }
    printf("%lld\n", cnt);
    for (ll i = 1; i <= cnt; ++i)
        printf("%lld%c", ans[i], i == cnt ? '\n' : ' ');
}

int main() {
    scanf("%lld", &n);
    for (ll i = 1; i <= n; ++i)
        scanf("%lld", &a[i]);
    solve_dp();
    solve_greedy();
    return 0;
}

suffix_lengths 是阶段 ①，default=0 处理"右边接不上"的情形；lex_smallest 是阶段 ②，候选条件与上面的两个不等式逐字对应，key=seq.__getitem__ 指明按值比较（键并列时 min 返回最先遇到的下标，即最靠前的那个）。solve 只负责读入、调用、输出。

复杂度

• 时间复杂度：$O(n^2)$。倒序 DP 对每个 $i$ 扫描右侧，共约 $\frac{n(n-1)}{2}$ 次比较；构造阶段最多 $L \leqslant n$ 步、每步 $O(n)$。$n = 300$ 时总计约 $1.4 \times 10^5$ 次比较，实测单组数据 0.017 s。
• 空间复杂度：$O(n)$。序列、$g$ 表与答案列表各占 $n$。

总结

本题的两个目标必须分开处理：长度最大是一次数值 DP，字典序最小是一次逐位构造。

关键一步是把 LIS 的状态从"以 $i$ 结尾"翻成"以 $i$ 开头"。$g_i$ 于是多了一层含义：它不只是长度，更是"从 $i$ 出发还能延伸多远"的潜力。有了这个潜力值，"选了某个元素之后还能不能凑满 $L$"这个问题就退化成一句不等式 $g_j \geqslant c$，逐位贪心的可行集因此完全可判。

顺着这个思路可以推广：任何"先定最优值、再求字典序最小方案"的题目，都可以先 DP 出每个位置的潜力，再逐位在可行集里取最小。当 $n$ 放大到 $10^5$ 时，把每步的朴素扫描换成对后缀最小值建线段树（按值离散化），整体可以做到 $O(n\log n)$，贪心结构完全不变。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5
6
7
8
9
10输入：n 个整数 a[1..n]
`- 目标：在所有最长不下降子序列里取字典序最小
   |- 阶段 1：倒序 DP 求潜力值
   |  `- g[i] = 以 a[i] 开头的最长不下降子序列长度   （O(n^2)）
   `- 阶段 2：逐位贪心构造
      |- 还差 c 个元素、已选末尾值 v、起点 p
      |- 候选 = { j >= p : g[j] >= c 且 a[j] >= v }
      |  `- g[j] >= c 用"潜力"保证后面一定填得满
      `- 在候选里取 a[j] 最小者，重复 c = L 次
         `- 答案：长度为 L 的值序列，字典序最小

先看"目标"这一层：长度最大与字典序最小是两个目标，必须按顺序拆开，这正是两个阶段的来源。再看阶段 2 的候选条件：$a_j \geqslant v$ 维持不下降，$g_j \geqslant c$ 用阶段 1 的潜力值保证后面还能补齐——少了它，贪心会在最后几步无解。最后看"取 $a_j$ 最小者"：比较键是值而不是下标，这由字典序的定义直接决定。