[NYIST16]矩形嵌套(DP,最长上升子序列)
2024-08-26 03:25:43
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=16
像套娃一样把矩形套起来。先给矩形从小到大排序,然后做最长上升子序列就行
/*
━━━━━┒ギリギリ♂ eye!
┓┏┓┏┓┃キリキリ♂ mind!
┛┗┛┗┛┃\○/
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%I64d", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(LL i = 0; i < (len); i++)
#define For(i, a, len) for(LL i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Fuint(a) memset((a), 0x7f7f, sizeof(a))
#define lrt rt << 1
#define rrt rt << 1 | 1
#define pi 3.14159265359
#define RT return
#define lowbit(x) x & (-x)
#define onenum(x) __builtin_popcount(x)
typedef long long LL;
typedef long double LD;
typedef unsigned long long Uint;
typedef pair<LL, LL> pii;
typedef pair<string, LL> psi;
typedef map<string, LL> msi;
typedef vector<LL> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; typedef struct Square {
int x, y;
Square() {}
Square(int xx, int yy) : x(xx), y(yy) {}
}Square; const int maxn = ;
Square s[maxn];
int n;
int dp[maxn]; bool cmp(Square a, Square b) {
if(a.x == b.x) return a.y <= b.y;
return a.x < b.x;
} bool ok(Square a, Square b) {
return a.x > b.x && a.y > b.y;
} int main() {
// FRead();
int T, x, y;
Rint(T);
W(T) {
Cls(dp);
Rint(n);
For(i, , n+) {
Rint(x); Rint(y);
if(x > y) swap(x, y);
s[i] = Square(x, y);
}
sort(s+, s+n+, cmp);
int ret = ;
For(i, , n+) {
dp[i] = ;
For(j, , i+) {
if(ok(s[i], s[j])) {
dp[i] = max(dp[i], dp[j]+);
}
}
ret = max(dp[i], ret);
}
printf("%d\n", ret+);
}
RT ;
}
最新文章
- 【java】Naming.bind和Registry.bind区别
- 强大的css3
- Android 保持Service不被Kill掉的方法--双Service守护 &;&; Android实现双进程守护
- Sublime Text 3 史上最性感的编辑器
- 7z 的命令行
- 情人节,教大家使用css画出一朵玫瑰花。
- 如何使用MFC连接Access数据库
- 异常-----web.xml文件报错 	Multiple annotations found at this line: 	- cvc-complex-type.2.4.b: The content of element &#39;welcome-file-list&#39; is not complete. One of &#39;{";http://java.sun.c
- PHP客服聊天
- TCP/IP协议(2):各层网络设备
- php -- 日期时间
- ActiveReports 报表应用教程 (10)---交互式报表之向下钻取(详细数据按需显示解决方案)
- cent7安装ffmpeg
- Hibernate一级缓存测试分析
- python 网页转pdf
- K8S从私有仓库拉取镜像
- 连续取模-function
- 程序4-4 chmod函数实例
- 【转】Monkey测试4——Monkey命令行可用的全部选项
- 修改const变量