程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 1471 Defense Lines (降低復雜度)

uva 1471 Defense Lines (降低復雜度)

編輯:C++入門知識

uva 1471 Defense Lines (降低復雜度)


題意:

給一個長度為n(n <= 200000) 的序列,你刪除一段連續的子序列,使得剩下的序列拼接起來,有一個最長的連續遞增子序列

思路:

設f[i] 和g[i] 分別表示 以i為開始 和 以i為結束 的最長連續遞增序列長度

首先可以想到枚舉i和j,然後計算max_len = f[i] + g[i];

但是這種枚舉方法的時間復雜度是O(n^2),這是在加上預處理f[i] 和g[i] 的前提下

所以需要想一個更加優化的方法,避免那麼多枚舉:

所以想到 只枚舉f[i], 通過某種方法快速的找到合適的 g[j]

在這個查找的過程中,首先可以排除掉一些不可能成為最優解的元素。這是一個常見的思路,在求解LIS的O(n*log(n))算法中,也用到了這種思路。

 

然後就是在查找的過程中,借助了數據結構中的SET來實現快速的插入(insert)和查詢(lower_bound )和查找(find),另外對其迭代器的正確操作也是很重要的(iterater)

code:

 

#include
#include
#include
#include
using namespace std;

typedef pair pii;
const int maxn = 200005;

int a[maxn],g[maxn],f[maxn];
set s;
int n;

void init(){
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
    }
    g[1] = 1;
    for(int i = 2; i <= n; i++){
        if(a[i] > a[i-1]) g[i] = g[i-1] + 1;
        else g[i] = 1;
    }
    f[n] = 1;
    for(int i = n-1; i >= 1; i--){
        if(a[i] < a[i+1]) f[i] = f[i+1] + 1;
        else f[i] = 1;
    }

    s.clear();
    s.insert(make_pair(a[1],g[1]));
    int ans = 1;
    for(int i = 2; i <= n; i++){
        pii c = make_pair(a[i],g[i]);
        set::iterator it = s.lower_bound(c);
        bool keep = true;
        if(it != s.begin()){
            pii last = *(--it);
            int len = f[i] + last.second;
            ans = max(ans, len);
            if(last.second >= c.second) keep = false;
        }

        if(keep){
            s.erase(c);
            s.insert(c);
            it = s.find(c);
            it++;
            while(it != s.end() && it->first > c.first && it->second <= c.second) s.erase(it++);
        }
    }
    printf("%d\n",ans);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        init();
//        solve();
    }
    return 0;
}

 

 

這道題目確實能讓我學到很多東西。包括思路方面,STL的使用上,以及對問題的預處理等等

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