最长上升子序列c++

Question

题意描述

给定一个1∼n的排列p和一个整数k，要求找到p的一个子序列 {pi1,pi2,⋯,pim}（1≤i1<i2<⋯<im≤n）满足： 恰好有k 个j满足1≤j≤m且pij是pi1,pi2,⋯,pim中从小往大数第j个。
如果有多解，输出任意一组解即可。如果不存在合法的子序列，输出−1。
输入格式
第一行两个整数n,k。 接下来一行 n 个整数p 1 ​ ,p 2 ​ ,⋯,p n ​ 表示给定的排列。
输出格式
如果无解，输出一行一个整数−1。 否则第一行输出一个整数 m 表示子序列的长度。你需要保证 1≤m≤n。 接下来一行输出 m 个整数 i 1 ​ ,i 2 ​ ,⋯,i m ​ 表示子序列的下标。你需要保证 1≤i j ​ ≤n 且 i j ​ <i j+1 ​ （ 1≤j<m）。
样例
输入
4 1
4 2 1 3
输出
3
2 3 4

我的思路

证明了一下，应该是最长上升子序列，但是不会写，所以请教一下大家，谢谢！

Answer 1

这个问题可以通过动态规划来解决，用以求解最长上升子序列（Longest Increasing Subsequence，简称 LIS）。在这个问题中，我们需要找到一个子序列，满足在这个子序列中有恰好 k 个数是严格递增的。

可以借助动态规划算法来解决。定义一个数组 dp，其中 dp[i] 表示以第 i 个数结尾的最长递增子序列的长度。初始化 dp[i] = 1，因为每个单独的元素都构成一个长度为 1 的递增子序列。

接下来，对于每个 i，我们需要考虑前面所有小于 i 的数 j，并检查是否可以将第 i 个数加入到以 j 结尾的递增子序列中，从而构成长度更长的递增子序列。状态转移方程为 dp[i] = max(dp[i], dp[j] + 1)，其中 j 的取值范围是 1 <= j < i 且 p[j] < p[i]。

完成动态规划后，从 dp 数组中找到最大值 max_length，表示最长递增子序列的长度。然后，反向回溯找到长度为 max_length 的子序列，并满足其中有恰好 k 个数是严格递增的。这个回溯过程可以通过记录状态转移时的路径来实现。

以下是基于这个思路的 C++ 代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }

    vector<int> dp(n + 1, 1);
    vector<int> pre(n + 1, -1); // 用于记录状态转移路径

    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            if (p[j] < p[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    pre[i] = j;
                }
            }
        }
    }

    int max_length = *max_element(dp.begin(), dp.end());
    if (max_length < k) {
        cout << -1 << endl;
    } else {
        vector<int> lis;
        int idx = distance(dp.begin(), find(dp.begin(), dp.end(), max_length));

        while (idx != -1) {
            lis.push_back(idx);
            idx = pre[idx];
        }

        reverse(lis.begin(), lis.end());
        
        cout << k << endl;
        for (int i = 0; i < k - 1; ++i) {
            cout << lis[i] << " ";
        }
        cout << lis[k - 1] << endl;
    }

    return 0;
}