題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1025
題意大概就是給你一大堆的城市，左邊的數(shù)表示這個(gè)城市缺什么物資，右邊的數(shù)表示那個(gè)物資從哪個(gè)城市往里運(yùn)，兩個(gè)城市之間需要鏈接道路，問(wèn)不交叉的情況下，最多能連多少條。這道題原本應(yīng)該是一個(gè)最長(zhǎng)公共子序列，但是無(wú)奈他給的數(shù)據(jù)范圍太大，LCS的做法明顯不滿(mǎn)足，所以首先我們可以把右邊的數(shù)映射到左邊來(lái)，這樣就轉(zhuǎn)化成求最長(zhǎng)不下降子序列的問(wèn)題，對(duì)于最長(zhǎng)不下降子序列，有一種DP+二分的求法，可以在nlogn的情況下完美解決。
思路大概就是dp數(shù)組記錄的是到當(dāng)前長(zhǎng)度的最靠前的元素，每遇到一個(gè)新元素，在dp數(shù)組中二分查找到小于它的最大元素的位置，在那里更新到它的最長(zhǎng)不下降子序列，這個(gè)算法牛逼就牛逼在二分那一步了，否則也不會(huì)做到nlogn的時(shí)間復(fù)雜度
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