AcWing 1012. 友好城市
原题链接
简单
作者:
胡歌-此生不换
,
2022-04-27 11:33:54
,
所有人可见
,
阅读 175
算法
(最长上升子序列模型) $O(n^2)$
参考文献
视频讲解
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
int a[N];
int f[N];
typedef pair<int, int> PII;
PII q[N];
int main(void)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> q[i].first >> q[i].second;
sort(q + 1, q + 1 + n); // 因为前面加了 1, 所以排序的时候要从 1 的位置开始排序
// 按第一的 first 进行排序的, 后面是在 second 里面找最大上升子序列的
// (因为理解题意, first 是排号序的,second 也是有序的,就符合题意不会有交叉的情况了)
int res = 0;
for(int i = 1; i <= n; i++)
{
f[i] = 1;
for(int j = 1; j < i; j++)
{
if(q[i].second > q[j].second) f[i] = max(f[i], f[j] + 1); // 理解题意之后就是模板题了
}
res = max(res, f[i]);
}
cout << res << endl;
return 0;
}