shuoj1936-D序列—最長上升子序列
Description
已知兩個長度為N的數組A和B，下標從0標號至N-1。
現在定義一種D序列 (假設長度為L)，這種序列滿足下列條件：
1. 0 <= D[i] <= N-1
2. A[D[i]] < A[D[i+1]] (0 <= i < L-1)
3. B[D[i]] > B[D[i+1]] (0 <= i < L-1)
求滿足條件的D序列的最大長度。
（其實這種序列叫做D序列的原因是：這道題是D題）
Input
多組數據，每組數據第一行是一個整數N。(1 <= N <= 100000)
第二行中有N個正整數A[0]~A[N-1]。
第三行中有N個正整數B[0]~B[N-1]。
保證所有輸入整數在int范圍內。
Output
對每組數據，輸出一個整數，表示D序列的最大長度L。
Sample Input
3 1 1 2 3 2 1 3 1 2 3 3 2 1 4 1 3 2 4 3 1 2 4
Sample Output
233
思路：：將A數組，B數組以A為第一關鍵字，B為第二關鍵字進行升序排序，然後將B倒置求B的最長上升子序列。 為了避免下標排序和寫比較函數，將A B 保存在pair裡先排序，然後再取出來存放大到 A 中。倒置，並求最長子序列。 在求最長上升子序列時，直接用dp的方法時間復雜度為 O(n^2),會超時，所以采用其他的方法求。 方法（1）：：利用lower_bound 求上升子序列O(nlogn) //lower_bound三個參數分別為要比較的起始點地址，終止點的地址+1（也就是左閉右開），要比較的值(假設為d)。 //它的作用是返回一個地址，這個地址是在比較的范圍內>=d的最小的值的地址。 //舉個例子，a[] = {0 , 1 ,2, 4, 5, 7 } p =lower_bound(a,a+6,3),p就為 4 的地址，如果p =lower_bound(a,a+6,4),p也為 4 的地址 方法（2）：：利用二分法求上升子序列O(nlogn) 利用lower_bound要在數組中進行比較，當要比較的數較大時，無法將數存放在數組中，而利用二分法能解決這一問題，但代碼難度較大。 兩種方法的思路是一樣的。將數組A中子序列長度為 i 的最小值存放在數組S中。我們以3 2 4 6 5 7 3 為例進行演示行為遍歷，列為數組S，變化的地方已經標出來，有助於理解。在這裡a[ i ] > s[ j ]&&a[i]<=s[ j + 1 ]就應該把a[ i ]放在s[ j+1 ]的位置。所以關鍵就是找出 j 就知道把a[ i ]放在哪了。上面的兩種方法就是用來尋找 j的 。（在這裡lower_bound直接返回 j + 1 ） 我們可以發現s數組中的值必然是有序遞增的，這也是可以利用二分法的一個必要條件。
演示
0
1
2
3
4
1
3
2
2
3
2
4
4
2
4
6
5
2
4
5
6
2
4
5
7
7
2
3
5
7
方法（1）代碼：：
#include
using namespace std;
int a[100005],b[100005];
int s[100005];
vector > T;//可以用vector存，也可以直接用數組 pair T[100005];
int main()
{
int n;
while(~scanf(%d,&n)){
T.clear();//如果不初始或要出錯用數組就不需要了
for(int i = 0;i第一個元素首先放入 s[1]
for(int i = 1;is[len])s[++len] = a[i];
else{
int p = lower_bound(s+1,s+len+1,t)-s;
s[p] = t;
}
}
printf(%d
,len);
}
return 0;
}
方法（2）代碼：：
#include
using namespace std;
int a[100005],b[100005];
int s[100005];
vector > T;
int main()
{
int n;
while(~scanf(%d,&n))
{
T.clear();
for(int i = 0;is[len]) s[++len] = a[i];
else{
int l = 1,r = len,mid;
int ans = 0;
while(l<=r)//這裡的二分法采用了左閉右閉的思路
{
mid = (r+l)/2;
if(s[mid]
