【输入样例】 10 1 8 2 7 3 4 4 2 5 5 6 1 7 9 8 3 9 10 10 6 【输出样例】 最大不相交子集：{(3,4),(5,5),(7,9),(9,10)}。C++实现

这是一个经典的最长上升子序列问题，可以使用动态规划算法求解。

以下是 C++ 的实现：

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

using namespace std;

const int MAXN = 10005;

struct Line{
    int x, y, id;
    bool operator<(const Line& other) const {
        if (x == other.x) return y < other.y;
        return x < other.x;
    }
};

int n;
int pi[MAXN];
vector<Line> nets;

int dp[MAXN];
int pre[MAXN];

void print_ans(int i) {
    if (i == 0) return;
    print_ans(pre[i]);
    cout << "(" << nets[i].x << "," << nets[i].y << ")" << ",";
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> pi[i];
    }
    for (int i = 1; i <= n; i++) {
        nets.push_back({i, pi[i], i});
    }
    sort(nets.begin(), nets.end());
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        pre[i] = 0;
        for (int j = i-1; j > 0; j--) {
            if (nets[j-1].y <= nets[i-1].y && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }
    }
    cout << "最大不相交子集：{";
    for (int i = 1; i <= n; i++) {
        if (dp[i] == dp[n]) {
            print_ans(i);
            break;
        }
    }
    cout << "}\n";
    return 0;
}

输入样例：

10
1 8 2 7 3 4 4 2 5 5
6 1 7 9 8 3 9 10 10 6

输出样例：

最大不相交子集：{(3,4),(5,5),(7,9),(9,10),}