5.在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连，如下图。其中，π(i),1≤ i ≤n，是｛1,2,…,n｝的一个排列。导线(i, π(i))称为该电路板上的第i条连线。对于任何1 ≤ i ≤ j ≤n，第i条连线和第j条连线相交的充要条件是π(i)>π(j)。在制作电路板时，要求将这n条连线分布到若干绝缘层上，在同一层上的连线不相交。现在要确定将哪些连线安排在一层上，使得该层上有尽可能多的连线，即确定导线集Nets = ｛(i，π(i))，1 ≤ i ≤ n｝的最大不相交子集。 【输入样例】 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 (y == other.y) return x < other.x;
        return y < other.y;
    }
};

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].id << ' ';
}

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] = dp[i-1];
        pre[i] = i-1;
        for (int j = i-1; j > 0; j--) {
            if (nets[j-1].y <= nets[i-1].x && 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 7 9 }