UVa10635 - Prince and Princess

出處 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1576

解題策略：最長遞增子序列，轉換成最長遞增子序列，將prince走的順序重新編碼為1到n^2，princess依照prince重新編號，如果不存在的編號就不編碼，求princess的最長遞增子序列長度就是答案，最長遞增子序列可以在O(n*log(n))解決。

數列A0,A1,A2,A3,..An-1求最長嚴格遞增的子序列長度，可以使用此方法，能在O(n*log(n))解決。

求最大嚴格遞增子序列長度

當i>p且i>q時，假設Ap < Aq，d(p)表示到Ap的最長嚴格遞增子序列的長度，當d(p)等於d(q)時，保留Ap即可。

假設陣列a[k]保留最長嚴格遞增子序列長度為k+1時的最小Ai，隨著不斷考慮新的Ai會不斷變動，但會獲得

a[0]<a[1]<a[2]<...a[k]<a[k+1] < ...。當考慮新的Ai只需要取lower_bound(a[0],a[最大深度],Ai)，a[]初始化為很大的數值，已排序的陣列a，取不小於Ai的最小索引值，即可以獲得Ai的深度，假設等於k，a[k]=Ai。取所有(k+1)的最大值就可以獲得答案。