计蒜客 T1408 矩形嵌套

2021/7/26 6:08:01

本文主要是介绍计蒜客 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 矩形嵌套的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程