题目关键是如何把不相交问题转化。
如果AB和A’B’相交,不妨设A<B,则必有A’>B’,也就是说,A’到B’是下降的
因此,对ABCD…从小到大排序,同时也把A’B’C’D’按ABCD的顺序排序,寻找A’B’C’D’中最长的上升子序列,序列长度就是答案。
#include <iostream>
#include <algorithm>
using namespace std;
int n, f[5005], ans;
struct node {
int c1, c2;
}c[5005];
bool cmp(const node &x, const node &y) {
return x.c1 < y.c1;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &c[i].c1, &c[i].c2);
}
sort(c, c + n, cmp);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (c[i].c2 > c[j].c2) {
f[i] = max(f[i], f[j] + 1);
}
}
ans = max(ans, f[i]);
}
printf("%d\n", ans + 1);
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁