友好城市 描述 Description 【问题描述】 Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。 每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。 【输入格式】 第1行，一个整数N(1<=N<=5000)，表示城市数。 第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。(0<=xi<=10000) 【输出格式】 仅一行，输出一个整数，政府所能批准的最多申请数。 【输入样例】 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 【输出样例】 4
一开始没有想出来，后来看了题解发现又是一道LIS（最长不下降子序列）。
首先可以把一边河岸排一下序。于是样例就变成了这样：
南岸北岸26429810315121717224由于南岸已经排好序，如果北岸批准的申请城市不是一个递增序列的话，一边递增，一边递减，就会交叉。所以问题就变成一个找北岸的最长不下降子序列。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct num{ int a; int b; }; bool compare(const num &x,const num &y) { if (x.a>y.a) return false; else return true; } int main() { freopen("data.in","r",stdin); int n; num s[5001]; cin>>n; for (int i=1;i<=n;++i) { cin>>s[i].a>>s[i].b; } sort(s+1,s+n+1,compare); const int hhh=n; int f[5001]={0}; for (int i=n;i>=1;i--) { int t=0; for (int j=i;j<=n;j++) { if (s[i].b<s[j].b&&f[j]>t) t=f[j]; } if (t==0) f[i]=1; else { f[i]=t+1; } } int max=0; for (int i=1;i<=n;i++)if (f[i]>max) max=f[i]; cout<<max; }