題目：uva10635Prince and Princess(LIS)
題目大意：求最長相同公共子序列。
解題思路：因為數據很大，62500不能用之前的那種求LIS的做法來做。可以將第一個路線的整數重新排個序（0...p)，然後之後的那個路線因為要找相同的最長子序列，所以要將它原來的數字映射成第一條路線新的數字。這樣之後就只需要找第二個路線的LIS就可以了。
nlog（n）的LIS算法：
普通的做法在查找的時候，需要for一遍找到比v【i】小的數。
用LIS數組來存放前i個數的最長LIS（top從0開始），那麼這樣數字有序就可以用二分查找（log（n））。如果v【i】 >LIS[top]的時候，代表可以加上v【i】 構成top + 1長度LIS。所以LIS【++top】 = v【i】， dp【i】 = top + 1；
如果等於的話，說明dp【i】 = top + 1；但是小於的話，需要在LIS找出一個大於等於v【i】的最接近v【i】的數（第k個），說明之前的k個數都是小於v【i】的。那麼dp【i】 = k + 1；但是這裡的LIS【k】要更新成v【i】。為什麼需要這樣？因為既然你要取k + 1個長度的遞增子序列，之前的k個都是相同的，那麼對於第k + 1個呢，應該取越小的越好把，因為這樣後面的數字才會有更大的可能接在這個子序列後面，構成更長的子序列。
代碼:
#include#include const int N = 62505; int dp[N]; int v[N]; int vis[N]; int LIS[N]; int p1; int Max (const int a, const int b) { return a > b ? a: b; } int bsearch (int s) { int l = 0; int r = p1; int mid; while (l < r) { mid = l + (r - l) / 2; if (s == LIS[mid]) return mid; else if (s > LIS[mid]) l = mid + 1; else r = mid; } return l; } int main () { int n, p, q, t; scanf ("%d", &t); for (int cas = 1; cas <= t; cas++) { scanf ("%d%d%d", &n, &p, &q); memset (vis, -1, sizeof (vis)); for (int i = 0; i <= p; i++) { scanf ("%d", &v[i]); vis[v[i]] = i; } p1 = -1; int k; int ans = 0; for (int i = 0; i <= q; i++) { scanf ("%d", &v[i]); v[i] = vis[v[i]]; if (v[i] == -1) continue; if (p1 == -1) { dp[i] = 1; LIS[++p1] = v[i]; } else { if (v[i] > LIS[p1]) { LIS[++p1] = v[i]; dp[i] = p1 + 1; } else if (v[i] < LIS[p1]) { k = bsearch (v[i]); dp[i] = k + 1; LIS[k] = v[i]; } else dp[i] = p1 + 1; } ans = Max (ans, dp[i]); } printf ("Case %d: %d\n", cas, ans); } return 0; }
