程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> UVA10635 Prince and Princess(LIS)

UVA10635 Prince and Princess(LIS)

編輯:關於C++

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


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved