//
// Created by Arc on 2020/4/27.
//对了，这篇题解的代码是小白自己写的．有啥错误还请各位大佬多多包涵． /*
* 某国有一条大河（一条大河~~~~，波浪宽~~~~),河有笔直的南北两岸，岸上各有位置不相同的n个城市
* 北岸的每个城市有且只有一个友好城市在南区
* 不同城市的友好城市不同（南北对应呗）
* 每对友好城市向政府申请开辟航道，但是为了交通安全，两条航道不能交叉
* 求政府最多可以建多少满足条件的航道
* 输入：
* 第一行为城市数：N
* 接下来一直到N+1行,分别表示南岸与北岸的坐标
* 输出：
* 批准数字以及路径（就是第几个城市）
*
*/
//话说小白看见这个题第一反应肯定是：不会啊．．．(菜习惯了),但是研究一下就会发现：
/*
* 要满足不交叉．． 其实也好办：只要把一边从大到小排序，另一边只要是升序就不会相交
* 1 3
* 2 4
* 3 1
* 4 5
* 5 2
*
* 但是如果是找最长的呢？
* 那就是右边的最长不下降序列啊！
*
* 所以：
* 排序加最长不下降．现在应该就会了吧！
*
*
*
*/
//存数我想用结构体，首先用sort进行排序，再进行最长不下降
#include <bits/stdc++.h>
using namespace std;
int N;
struct Friend{
int x;
int y;
}friends[];
struct Rule{//sort自定义比较规则
bool operator()(const Friend &f1,const Friend &f2)
{
return f1.x < f2.x;
}
};
int f[];
int c[]={};
int main(){
cin>>N;
for (int i = ; i <= N; ++i) {//注意下标从１开始，是１到N
cin>>friends[i].x>>friends[i].y;
} sort(friends+,friends++N,Rule());//sort排序 for (int i = ; i <= N; ++i) {
cout<<friends[i].x<<" "<<friends[i].y<<endl;
} f[N]=;//注意，一般是有对最后一个值赋值的语句
int k;
for (int j = N-; j >= ; j--) {
int l=;//记录每一次固定点的最大值
k=;
for (int i = j+; i <= N ; ++i) {
if(f[i]>l && (friends[j].y < friends[i].y )){//两个条件：大于，且是后面的数的最大值
l=f[i];
k=i;
} }
f[j]=l+;
c[j]=k;//记录位置 }
int p=;
for (int m = ; m <= N ; ++m) {//寻找最大不下降
if(f[p]<f[m])
p=m;
}
cout<<f[p]<<endl;
//以下的几行几乎就是输出路径的套路，非常建议背过
cout<<p;
p=c[p];
while(p!=){
cout<<"-";
cout<<p;
p=c[p];
} }
做个小笔记：
一开始给数组命名成了friend直接报错，为啥呢？后来忽然想起friend是c++的一个关键字（友元），所以我很淡定地改成了friends.其实命名的时候，加个复数可能会回避一些自己不知道的关键字．
再就是注意对最后一个f[n]的赋值吧！
最后几行是输出路径的套路了．．．．嗯嗯．