题解 | #马戏团# 动态规划-最长递减子序列

题目的题意有点难以理解，参考了讨论区大佬的解读：

1.如果两人体重不一样，则上面的身高要小于等于下面的身高

2.如果两人体重一样，那么他们的身高也必须一样

先按照体重降序排列，再对得到的序列按照身高求最长递减子序列

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

int main() {
    int N;
    while (cin >> N) {
        vector<pair<int, int>> data;
        int id, weight, height;
        for (int i = 0; i < N; i++) {
            cin >> id >> weight >> height;
            data.emplace_back(weight, height);
        }
        sort(data.begin(), data.end(), [&](const auto & a, const auto & b) {
            if (a.first == b.first) {
                return a.second < b.second; // 体重相同时，身高小的排前面
            } else {
                return a.first > b.first;
            }
        });
        // 最长递减子序列
        vector<int> dp(N, 1);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (data[j].second >= data[i].second) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
    return 0;
}

时间复杂度：O(N^2)，用于生成最长递减子序列

空间复杂度：O(N)，用于数组的空间