Sequence two

题目解析

题目大意： 给定一个包含 $N$ ( $N \le 100$ ) 个整数的序列。你需要找到前 $P$ 个满足“非递减”性质的子序列。输出的排序规则如下：

长度优先：长度短的子序列排在前面（即先输出长度为1的，再输出长度为2的……）。
字典序优先：长度相同的子序列，按字典序（数值大小）从小到大排序。
如果满足条件的子序列总数少于 $P$ ，则输出所有满足条件的子序列。

输入： 多组测试数据。每组包含 $N$ 和 $P$ ，随后一行是 $N$ 个整数。

输出： 按上述规则输出子序列，每个测试用例结束后输出一个空行。

解题思路

这就要求我们在搜索子序列时，必须严格控制搜索顺序。

确定遍历顺序（最外层）： 题目要求按长度排序，所以我们最外层循环应该是枚举子序列的长度 $L$ ，从 $1$ 到 $N$ 。
确定搜索策略（DFS）： 对于固定的长度 $L$ ，我们需要找到所有长度为 $L$ 的非递减子序列，并按字典序输出。我们可以使用 DFS（深度优先搜索）来构建子序列。 DFS(last_index, current_length, target_length)：
- last_index: 上一个选中的元素在原数组中的下标。
- current_length: 当前已经选了几个数。
- target_length: 目标长度 $L$ 。
保证字典序和去重（关键点）： 在 DFS 的每一步，我们需要决定下一个元素选谁。假设上一个选的下标是 last_index，那么下一个下标 $i$ 必须满足：
- $i > last\_index$ （下标递增）
- $arr[i] \ge arr[last\_index]$ （数值非递减）
- 可行性剪枝：以 $i$ 开头是否能凑够剩余所需的长度？这需要预处理 DP。
为了保证字典序最小，我们在每一步选下一个数时，不能简单地按原来的下标顺序遍历，而应该将所有合法的候选元素按数值从小到大排序，然后依次尝试。

同时，为了去重（例如输入 1 2 2，长度为1的子序列应该是 1, 2，而不是 1, 2, 2），在排序后的候选列表中，如果当前元素的值与上一个尝试的元素值相同，则跳过。
可行性预处理 (DP)： 为了避免走进死胡同（选了某个数，结果后面凑不够长度了），我们需要先计算一个数组 dp[i]，表示以第 $i$ 个元素开头的最长非递减子序列的长度。
- 状态转移： $dp[i] = 1 + \max( \{dp[j] \mid j > i \text{ 且 } arr[j] \ge arr[i]\} \cup \{0\} )$ 。
- 在 DFS 选择下一个节点 $k$ 时，必须满足 dp[k] >= target_length - current_length - 1，否则选了 $k$ 也凑不够长度，直接剪枝。

代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, p;
int a[105];
int dp[105]; // dp[i] 表示以 a[i] 开头的最长非递减子序列长度
vector<int> path; // 记录当前路径

// 预处理 DP
void calc_dp() {
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (a[j] >= a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
}

struct Node {
    int val; // 具体的数值
    int id;  // 原数组中的下标
};

// 比较函数：数值小的优先；数值相同，下标小的优先（虽然去重后下标次要，但排序需稳定）
bool cmp(const Node& x, const Node& y) {
    if (x.val != y.val) return x.val < y.val;
    return x.id < y.id;
}

// DFS 搜索
// last_idx: 上一个选取的元素下标（-1表示还没选）
// target_len: 本次搜索的目标长度
void dfs(int last_idx, int target_len) {
    if (p == 0) return; // 已经找够 P 个，直接退出

    int cur_len = path.size();
    if (cur_len == target_len) {
        // 找到了一个符合长度的序列，打印
        for (int i = 0; i < cur_len; i++) {
            cout << path[i] << (i == cur_len - 1 ? "" : " ");
        }
        cout << endl;
        p--;
        return;
    }

    // 收集所有可能的下一个候选项
    vector<Node> candidates;
    int start = last_idx + 1;
    
    for (int i = start; i < n; i++) {
        // 1. 满足非递减性质
        if (last_idx != -1 && a[i] < a[last_idx]) continue;
        
        // 2. 满足长度可行性（剪枝）
        // 如果从 i 开始的最长长度 + 当前已有长度 < 目标长度，则不能选 i
        if (dp[i] + cur_len < target_len) continue;

        candidates.push_back({a[i], i});
    }

    // 按数值排序，保证字典序最小
    sort(candidates.begin(), candidates.end(), cmp);

    // 遍历候选项
    for (int i = 0; i < candidates.size(); i++) {
        if (p == 0) return;

        // 去重：如果当前值的数值和上一个候选项相同，则跳过
        // 因为排序过，相同的数值是相邻的，且因为我们优先选了下标小的（在sort中隐含或自然顺序），
        // 如果下标小的那个能搜出结果，下标大的那个搜出的结果必然是重复的或者被包含的。
        // 这里的去重是为了防止同一层级选了数值相同的不同元素导致输出重复的序列。
        if (i > 0 && candidates[i].val == candidates[i-1].val) continue;

        // 递归
        path.push_back(candidates[i].val);
        dfs(candidates[i].id, target_len);
        path.pop_back(); // 回溯
    }
}

int main() {
    // 优化IO
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n >> p) {
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        calc_dp();

        // 外层循环：枚举长度
        for (int len = 1; len <= n; len++) {
            if (p == 0) break;
            path.clear();
            dfs(-1, len);
        }
        
        cout << endl; // 每个 case 后输出空行
    }
    return 0;
}

题目难度与评价

难度评级：中等偏下 (Medium-Low)

考察点：
- 深度优先搜索 (DFS)：用于构建序列。
- 动态规划 (DP) 思想：用于可行性剪枝（Look-ahead），判断当前节点是否有潜力构成目标长度的序列。如果没有这个剪枝，盲目搜索在最坏情况下会超时。
- 排序与去重：这道题最核心的难点在于输出顺序。为了满足“字典序最小”，不能简单地按数组下标顺序 DFS，而必须在每一步将所有合法的“下一步”按数值排序。同时需要处理重复元素的情况。
易错点：
- 输出格式：很容易忽略题目要求的长度优先，即必须外层循环枚举长度 $1 \to N$ 。
- 字典序逻辑：如果直接按数组下标遍历，得到的不是字典序最小的。例如 1 3 2，按下标遍历会先得到 1 3，然后回溯得到 1 2。但题目要求 1 2 在前。必须在搜索树的每一层对候选项进行排序。
- 空行：Presentation Error 的常见来源。
总结： 这是一道非常经典的搜索题目，它结合了最基础的 LIS（最长上升子序列）的 DP 预处理思想和带有特定顺序要求的 DFS 回溯。对于训练搜索剪枝和字典序构建非常有帮助。虽然 $N$ 很小，但 $P$ 较大，考验了代码逻辑的准确性和剪枝的有效性。

目录

题目解析

解题思路

代码实现

题目难度与评价