题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1025
题意大概就是给你一大堆的城市，左边的数表示这个城市缺什么物资，右边的数表示那个物资从哪个城市往里运，两个城市之间需要链接道路，问不交叉的情况下，最多能连多少条。这道题原本应该是一个最长公共子序列，但是无奈他给的数据范围太大，LCS的做法明显不满足，所以首先我们可以把右边的数映射到左边来，这样就转化成求最长不下降子序列的问题，对于最长不下降子序列，有一种DP+二分的求法，可以在nlogn的情况下完美解决。
思路大概就是dp数组记录的是到当前长度的最靠前的元素，每遇到一个新元素，在dp数组中二分查找到小于它的最大元素的位置，在那里更新到它的最长不下降子序列，这个算法牛逼就牛逼在二分那一步了，否则也不会做到nlogn的时间复杂度
view code
1 #include <cstdio>
2 #include <cstring>
3 const int maxn = 500100;
4 int dp[maxn], a[maxn], n;
5 int lis(){
6 dp[1] = a[1];
7 int len = 1;
8 for (int i = 2; i <= n; i++){
9 int l = 1, r = len;
10 while (l <= r){
11 int m = (l + r) >> 1;
12 if (a[i] > dp[m]) l = m + 1;
13 else r = m - 1;
14 }
15 dp[l] = a[i];
16 if (l > len) len = l;
17 }
18 return len;
19 }
20 int main(){
21 int p = 1;
22 while (~scanf("%d", &n)){
23 for (int i = 0; i < n; i++){
24 int x, y;
25 scanf("%d%d", &x, &y);
26 a[x] = y;
27 }
28 memset(dp, 0, sizeof(dp));
29 int ans = lis();
30 printf("Case %d:\nMy king, at most %d road", p++, ans);
31 if (ans > 1) printf("s");
32 printf(" can be built.\n\n");
33 }
34 return 0;
35