计蒜客 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 矩形嵌套的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程