<Mysterious Present>

<Mysterious Present>题解

#include <bits/stdc++.h>
using namespace std;

struct Envelope {
    int w, h, id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, w0, h0;
    cin >> n >> w0 >> h0;

    vector<Envelope> envs;
    for (int i = 1; i <= n; i++) {
        int wi, hi;
        cin >> wi >> hi;
        if (wi > w0 && hi > h0) {
            envs.push_back({wi, hi, i});
        }
    }

    if (envs.empty()) {
        cout << 0 << "\n";
        return 0;
    }

    sort(envs.begin(), envs.end(), [](const Envelope& a, const Envelope& b) {
        if (a.w != b.w) return a.w < b.w;
        return a.h < b.h;
    });

    int m = envs.size();
    vector<int> dp(m, 1), pre(m, -1);

    int max_len = 0, best_idx = -1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < i; j++) {
            if (envs[j].w < envs[i].w && envs[j].h < envs[i].h) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    pre[i] = j;
                }
            }
        }
        if (dp[i] > max_len) {
            max_len = dp[i];
            best_idx = i;
        }
    }

    cout << max_len << "\n";
    vector<int> path;
    while (best_idx != -1) {
        path.push_back(envs[best_idx].id);
        best_idx = pre[best_idx];
    }
    reverse(path.begin(), path.end());
    for (size_t i = 0; i < path.size(); i++) {
        if (i > 0) cout << " ";
        cout << path[i];
    }
    cout << "\n";

    return 0;
}