題意:王子和公主同時從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; }