计蒜客 T1408 矩形嵌套

本文主要是介绍计蒜客 T1408 矩形嵌套，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：计蒜客 T1408 矩形嵌套

题目大意：

题解：
按宽对矩形从小到大排序，宽相等的矩形长更大的在前面，再对矩形的长计算最长升。

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

int dp[1010], len, n, t;
struct Node {
    int l, w;
    bool operator<(const Node &obj) const {
        if (l == obj.l) {
            return w > obj.w;
        }
        return l < obj.l;
    }
} a[1010];

int main() {
    cin >> t;
    while (t--) {
        len = 0;
        cin >> n;
        for (int i = 1, x, y; i <= n; ++i) {
            cin >> x >> y;
            a[i].l = max(x, y);
            a[i].w = min(x, y);
        }
        sort(a + 1, a + n + 1);
        dp[++len] = a[1].w;
        for (int i = 2; i <= n; ++i) {
            if (dp[len] < a[i].w) {
                dp[++len] = a[i].w;
            } else {
                int p = lower_bound(dp + 1, dp + len + 1, a[i].w) - dp;
                dp[p] = a[i].w;
            }
        }
        cout << len << endl;
    }
    return 0;
}

这篇关于计蒜客 T1408 矩形嵌套的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！