1 // 2 // Created by Arc on 2020/4/27. 3 //对了，这篇题解的代码是小白自己写的．有啥错误还请各位大佬多多包涵． 4 5 /* 6 * 某国有一条大河（一条大河~~~~，波浪宽~~~~),河有笔直的南北两岸，岸上各有位置不相同的n个城市 7 * 北岸的每个城市有且只有一个友好城市在南区 8 * 不同城市的友好城市不同（南北对应呗） 9 * 每对友好城市向政府申请开辟航道，但是为了交通安全，两条航道不能交叉 10 * 求政府最多可以建多少满足条件的航道 11 * 输入： 12 * 第一行为城市数：N 13 * 接下来一直到N+1行,分别表示南岸与北岸的坐标 14 * 输出： 15 * 批准数字以及路径（就是第几个城市） 16 * 17 */ 18 //话说小白看见这个题第一反应肯定是：不会啊．．．(菜习惯了),但是研究一下就会发现： 19 /* 20 * 要满足不交叉．． 其实也好办：只要把一边从大到小排序，另一边只要是升序就不会相交 21 * 1 3 22 * 2 4 23 * 3 1 24 * 4 5 25 * 5 2 26 * 27 * 但是如果是找最长的呢？ 28 * 那就是右边的最长不下降序列啊！ 29 * 30 * 所以： 31 * 排序加最长不下降．现在应该就会了吧！ 32 * 33 * 34 * 35 */ 36 //存数我想用结构体，首先用sort进行排序，再进行最长不下降 37 #include <bits/stdc++.h> 38 using namespace std; 39 int N; 40 struct Friend{ 41 int x; 42 int y; 43 }friends[100]; 44 struct Rule{//sort自定义比较规则 45 bool operator()(const Friend &f1,const Friend &f2) 46 { 47 return f1.x < f2.x; 48 } 49 }; 50 int f[100]; 51 int c[100]={0}; 52 int main(){ 53 cin>>N; 54 for (int i = 1; i <= N; ++i) {//注意下标从１开始，是１到N 55 cin>>friends[i].x>>friends[i].y; 56 } 57 58 sort(friends+1,friends+1+N,Rule());//sort排序 59 60 for (int i = 1; i <= N; ++i) { 61 cout<<friends[i].x<<" "<<friends[i].y<<endl; 62 } 63 64 f[N]=1;//注意，一般是有对最后一个值赋值的语句 65 int k; 66 for (int j = N-1; j >=1 ; j--) { 67 int l=0;//记录每一次固定点的最大值 68 k=0; 69 for (int i = j+1; i <= N ; ++i) { 70 if(f[i]>l && (friends[j].y < friends[i].y )){//两个条件：大于，且是后面的数的最大值 71 l=f[i]; 72 k=i; 73 } 74 75 } 76 f[j]=l+1; 77 c[j]=k;//记录位置 78 79 80 } 81 int p=1; 82 for (int m = 2; m <= N ; ++m) {//寻找最大不下降 83 if(f[p]<f[m]) 84 p=m; 85 } 86 cout<<f[p]<<endl; 87 //以下的几行几乎就是输出路径的套路，非常建议背过 88 cout<<p; 89 p=c[p]; 90 while(p!=0){ 91 cout<<"-"; 92 cout<<p; 93 p=c[p]; 94 } 95 96 97 }
做个小笔记：
一开始给数组命名成了friend直接报错，为啥呢？后来忽然想起friend是c++的一个关键字（友元），所以我很淡定地改成了friends.其实命名的时候，加个复数可能会回避一些自己不知道的关键字．
再就是注意对最后一个f[n]的赋值吧！
最后几行是输出路径的套路了．．．．嗯嗯．