倒卖战利品

> 首先要注意，题目中的条件有误，应该是严格大于而不是大于等于。

排序+动态规划（暴力搜索）

首先按照第一个维度将数组从小到大排序，第一个维度相同的，按照第二个维度从小到达排序。这样以来，问题就被转换为最大上升子序列问题。使用动态规划求解即可。
状态定义为：以第i个元素结尾的上升子序列的最大长度。
下面是第一种动态规划的解法，该解法超时。

#include <vector>
#include <iostream>
#include <limits.h>
#include <functional>
#include <algorithm>

using namespace std;

struct Compare {
    bool operator () (const vector<int>& item1, const vector<int>& item2) {
        if (item1[0] == item2[0]) {
            return item1[1] < item2[1];
        } else {
            return item1[0] < item2[0];
        }
    }
};

int main() {
    int n;
    cin >> n;
    vector<vector<int>> items(n, vector<int>(2, 0));
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &items[i][0], &items[i][1]);
    }

    sort(items.begin(), items.end(), Compare());

    vector<int> dp_table(n, 1);

    int max_sold = 1;
    for (int i = 1; i < n; i++) {
        int current_max_length = 1;
        int length;
        for (int j = 0; j < i; j++) {
            if (items[i][1] <= items[j][1]) {
                continue;
            }

            length = dp_table[j] + 1;
            if (length > current_max_length) {
                current_max_length = length;
            }
        }

        if (current_max_length > max_sold) {
            max_sold = current_max_length;
        }

        dp_table[i] = current_max_length;
    }

    cout << max_sold << endl;
    return 0;
}

排序+动态规划（二分查找+贪心）

在动态规划中，为了更快地进行查找，需要更改状态定义。将状态dp[i]定义为长度为i + 1的上升子序列的尾元素的最小值。在进行状态转移时，比较复杂，建议参考最长上升子序列。
代码如下：

#include <vector>
#include <iostream>
#include <limits.h>
#include <functional>
#include <algorithm>

using namespace std;

struct Compare {
    bool operator () (const vector<int>& item1, const vector<int>& item2) {
        if (item1[0] == item2[0]) {
            return item1[1] < item2[1];
        } else {
            return item1[0] < item2[0];
        }
    }
};

int main() {
    int n;
    cin >> n;
    vector<vector<int>> items(n, vector<int>(2, 0));
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &items[i][0], &items[i][1]);
    }

    sort(items.begin(), items.end(), Compare());

    vector<int> dp_table(n, 0);  // dp_table[i]表示长度为i + 1的上升子序列末尾的最小值

    dp_table[0] = items[0][1];

    int end = 0;
    for (int i = 1; i < n; i++) {
        if (items[i][1] > dp_table[end]) {
            end++;
            dp_table[end] = items[i][1];
        } else {
            int left = 0;
            int right = end;
            while (left < right) {  // 在dp_table中查找第一个大于items[i][1]的数
                int mid = left + (right - left) / 2;
                if (items[i][1] > dp_table[mid]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            dp_table[left] = items[i][1];
        }
    }

    end++;
    cout << end << endl;
    return 0;
}
}