题目链接：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[500010]; int n; int Lis[500010]; int cas = 0; void LIS() //求最大递增子序列 { //int Lis[500010]; //这个这么大的数组不能定义在子函数里，否则会运行不了，无语 int len = 0; memset(Lis, 0, sizeof(Lis)); for (int i = 1; i <= n; i++) { if (arr[i] > Lis[len])Lis[++len] = arr[i]; else { int j = lower_bound(Lis + 1, Lis + len + 1, arr[i]) - Lis; Lis[j] = arr[i]; } } printf("Case %d: ", ++cas); if(len==1)printf("My king, at most %d road can be built. ",len); //哇，这里好坑啊，原来只有一条路的时候road用单数，多条路用复数 else printf("My king, at most %d roads can be built. ", len); } int main() { while (~scanf("%d", &n)) { memset(arr, 0, sizeof(arr)); int a, b; for (int i = 1; i <= n; i++) { scanf("%d %d", &a, &b); arr[a] = b; //将城市之间的连线形象的转变成，将b看成a城市的值，然后就将这道题转变为了简单的LIS } LIS(); } return 0; }
2018-05-17