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

shuoj1936

編輯:關於C++

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]

 

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