C++题目描述给你 �N 对数 �1�1……����A 1 B 1 ……A n B n 。要求你从中找出最多的对把它们按照一种方式排列重新标号 12�12k。能满足对于每一对 ��ij 都有 ����A i B j 。输入格式第一行给出一个数字 �N�=100000N=100000下面 �N 行分别给出 ����A i B i 其小于 10910 9 输出格式输出 �K 的极大值输

思路：

1. 首先按照A升序排序，如果A相等，则按照B降序排序，这样可以保证对于每一对<Ai, Bj>，Ai > Bj。
2. 然后从排序后的数对中找出最长的递增序列。
3. 输出递增序列的长度即为极大值K。

C++实现：

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

bool compare(pair<int, int> p1, pair<int, int> p2) {
    if (p1.first == p2.first)
        return p1.second > p2.second; // 如果A相等，则按照B降序排序
    else
        return p1.first < p2.first; // 按照A升序排序
}

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i].first >> nums[i].second;
    }
    sort(nums.begin(), nums.end(), compare); // 排序
    vector<int> dp(N, 1); // dp[i]表示以第i个数对结尾的最长递增序列的长度
    int maxLen = 1; // 最长递增序列的长度
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i].second > nums[j].second) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    cout << maxLen << endl;
    return 0;
}
``