题目链接：https://vjudge.net/contest/228455#problem/A
题目大意：
有2n个城市，其中有n个富有的城市，n个贫穷的城市，其中富有的城市只在一种资源富有，且富有的城市之间富有的资源都不相同，贫穷的城市只有一种资源贫穷，且各不相同，现在给出一部分贫穷城市的需求，每个需求都是一个贫穷的向一个富有的城市要资源，且每个富有的城市都想向贫穷的城市输入自己富有的那部分资源，现在为了运输要建设多条路，但是路与路之间不允许有交叉，求满足贫穷城市的各种要求最多可以建设多少条路。
解题分析：
此题的难点在于很难看出求城市之间连线的最大值实际上就是，将a城市看成数组，每一个a城市对应的b城市看成a数组的对应值，然后就是求出a城市数组的最长上升子序列的长度。因为要使城市之间的连线不交叉的数量最多，很明显就是要求斜向一个同方向的线条（线条方向分为两种，斜向左和斜向右）最多，即求a数组的最长上升子序列。
记住了最长上升子序列如果要求严格上升的话就是lower_bound 可以相等的话就是upper_bound
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int arr[]; int n;
int Lis[];
int cas = ;
void LIS() //求最大递增子序列
{
//int Lis[500010]; //这个这么大的数组不能定义在子函数里，否则会运行不了，无语
int len = ;
memset(Lis, , sizeof(Lis));
for (int i = ; i <= n; i++)
{
if (arr[i] > Lis[len])Lis[++len] = arr[i];
else
{
int j = lower_bound(Lis + , Lis + len + , arr[i]) - Lis;
Lis[j] = arr[i];
}
}
printf("Case %d:\n", ++cas);
if(len==)printf("My king, at most %d road can be built.\n\n",len); //哇，这里好坑啊，原来只有一条路的时候road用单数，多条路用复数
else
printf("My king, at most %d roads can be built.\n\n", len);
} int main()
{
while (~scanf("%d", &n))
{
memset(arr, , sizeof(arr));
int a, b;
for (int i = ; i <= n; i++) {
scanf("%d %d", &a, &b);
arr[a] = b; //将城市之间的连线形象的转变成，将b看成a城市的值，然后就将这道题转变为了简单的LIS
}
LIS();
}
return ;
}
2018-05-17