1012. 友好城市
题意
Palmia 国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。
北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。
每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。
编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。
思路
对于北岸的城市若想满足题目要求 必须要满足左边城市对应的南岸城市的坐标 大于 右边城市对应的南岸城市的坐标 容易想到是一个最长递增子序列问题
先将绑定的两个城市用 struct 存在一起 然后分别按照北岸和南岸城市排序 排序后求对岸的最长递增子序列即可
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 6000; int n; int f[N]; struct Node { int a, b; }node[N]; bool cmp1(Node a, Node b) { return a.a < b.a; } bool cmp2(Node a, Node b) { return a.b < b.b; } void solve() { cin >> n; for (int i = 1; i <= n; ++i) { scanf("%d%d", &node[i].a, &node[i].b); } sort(node + 1, node + 1 + n, cmp1); for (int i = 1; i <= n; ++i) { f[i] = 1; for (int j = 1; j <= i; ++j) if (node[j].b < node[i].b) f[i] = max(f[i], f[j] + 1); } int res = -INF; for (int i = 1; i <= n; ++i) { res = max(res, f[i]); } sort(node + 1, node + 1 + n, cmp2); for (int i = 1; i <= n; ++i) { f[i] = 1; for (int j = 1; j <= i; ++j) if (node[j].a < node[i].a) f[i] = max(f[i], f[j] + 1); } for (int i = 1; i <= n; ++i) { res = max(res, f[i]); } cout << res << endl; } int main() { //int t; cin >> t; //while (t--) solve(); return 0; }
