題意：王子和公主同時從1出發走到 n*n， 求他們兩個路徑的最長公共子序列；
思路：因為這題n有250，如果用LCS負責度為O(n^2),容易超時，於是我們選擇它的優化版Lis算法來求最長公共子序列，這樣我們的復雜度就降為O(n*logn)了。
Lis算法：
先回顧經典的O(n^2)的動態規劃算法，設A[t]表示序列中的第t個數，F[t]表示從1到t這一段中以t結尾的最長上升子序列的長度，初始時設F[t] = 0(t = 1, 2, ..., len(A))。則有動態規劃方程：F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。
現在，我們仔細考慮計算F[t]時的情況。假設有兩個元素A[x]和A[y]，滿足
(1)x < y < t (2)A[x] < A[y] < A[t] (3)F[x] = F[y]
此時，選擇F[x]和選擇F[y]都可以得到同樣的F[t]值，那麼，在最長上升子序列的這個位置中，應該選擇A[x]還是應該選擇A[y]呢？
很明顯，選擇A[x]比選擇A[y]要好。因為由於條件(2)，在A[x+1] ... A[t-1]這一段中，如果存在A[z]，A[x] < A[z] < a[y]，則與選擇A[y]相比，將會得到更長的上升子序列。
再根據條件(3)，我們會得到一個啟示：根據F[]的值進行分類。對於F[]的每一個取值k，我們只需要保留滿足F[t] = k的所有A[t]中的最小值。設D[k]記錄這個值，即D[k] = min{A[t]} (F[t] = k)。
注意到D[]的兩個特點：
(1) D[k]的值是在整個計算過程中是單調不上升的。
(2) D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。
利用D[]，我們可以得到另外一種計算最長上升子序列長度的方法。設當前已經求出的最長上升子序列長度為len。先判斷A[t]與D[len]。若A[t] > D[len]，則將A[t]接在D[len]後將得到一個更長的上升子序列，len = len + 1， D[len] = A[t]；否則，在D[1]..D[len]中，找到最大的j，滿足D[j] < A[t]。令k = j + 1，則有D[j] < A[t] <= D[k]，將A[t]接在D[j]後將得到一個更長的上升子序列，同時更新D[k] = A[t]。最後，len即為所要求的最長上升子序列的長度。
代碼如下：
#include#include #include #include using namespace std; const int maxn=250*250+10; int n, p, q, a; int prince[maxn], princess[maxn]; int arr[maxn]; int Lis(int n) { int len=0; memset(arr, 0, sizeof(arr)); for(int i=1; i<=n; i++) { int l=1, r=len; while(l<=r) { int mid=(l+r)>>1; if(prince[i]>arr[mid]) l=mid+1; else r=mid-1; } arr[l]=prince[i]; if(l>len) len=l; } return len; } int main() { int t=0; scanf("%d", &t); int cas=1; while(t--) { scanf("%d%d%d", &n, &p, &q); memset(prince, 0, sizeof(prince)); memset(princess, 0, sizeof(princess)); p++, q++; for(int i=1; i<=p; i++) { scanf("%d", &prince[i]); } for(int i=1; i<=q; i++) { scanf("%d", &a); princess[a]=i; } for(int i=1; i<=p; i++) { prince[i]=princess[prince[i]]; } printf("Case %d: %d\n", cas, Lis(p)); cas++; } return 0; }
