程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [UVA]10534 - Wavio Sequence（LIS最長上升子序列）

[UVA]10534 - Wavio Sequence（LIS最長上升子序列）

編輯：C++入門知識

[UVA]10534 - Wavio Sequence（LIS最長上升子序列）

這題一看10000的數據量就知道必須用nlog(n)的時間復雜度。

所以特意去看了最長上升子序列的nlog(n)的算法。

如果有2個位置，該位置上的元素為A[i]和A[j],並且他們滿足以下條件:

1.dp[i] = dp[j] (dp[x]代表以x結尾的最長上升子序列長度)

2.A[i] < A[j]

3.i < j

那麼毫無疑問，選擇dp[i] 一定優於選擇dp[j]

那麼我們可以利用g[i]表示長度為i的序列的最後一個元素的最小值.

每次拿到一個A[i],在g[i]裡面尋找到一個元素，使得g[t] >= A[i].

dp[i] = t;

之後更新最小值 g[t] = A[i];

求最大下降子序列的話返回來遍歷一遍就行了。

之後 ans = max(ans, min(dp[i],dp[j]) * 2 - 1);

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define _PI acos(-1.0)
typedef long long LL;
typedef unsigned long long ULL;
typedef pair pill;
/*======================================
======================================*/
#define MAXD 10010
#define INF (1 << 30)
void LIS1(int dp[],int A[],int n){
    int g[MAXD];
    for(int i = 1 ; i <= n ; i++) g[i] = INF;
    for(int i = 1 ; i <= n ; i++){
        int k = lower_bound(g + 1 , g + n + 1 , A[i]) - g;
        dp[i] = k;
        g[k] = A[i];
    }
    return ;
}
void LIS2(int dp[],int A[],int n){
    int g[MAXD];
    for(int i = 1 ; i <= n ; i++) g[i] = INF;
    for(int i = n ; i >= 1 ; i--){
        int k = lower_bound(g + 1 , g + n + 1 , A[i]) - g;
        dp[i] = k;
        g[k] = A[i];
    }
    return ;
}
int main(){
    int n;
    int A[MAXD];
    while(scanf("%d",&n) != EOF){
        for(int i = 1 ; i <= n ; i++)
            scanf("%d",&A[i]);
        int dp1[MAXD] , dp2[MAXD];
        LIS1(dp1,A,n);
        LIS2(dp2,A,n);
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++){
            int t = min(dp1[i],dp2[i]);
            ans = max(ans,2 * t - 1);
        }
        printf("%d\n",ans);
    }
    return 0;
}