[LIS] 백준 4198 :: 열차정렬

열차정렬 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1238	246	166	21.364%

문제

에린은 엔지니어이자, 기차를 운전하는 기관사입니다. 또한 그녀는 각 열차를 구성하는 차량을 배열하는 일도 합니다. 그녀는 차량들을 정렬할 때, 열차의 전면에 가장 무거운 차량을 놓고, 후미로 갈수록 중량이 감소하는 순서로 차량을 넣는 것을 좋아합니다.

불행하게도, 차량을 배열하는 일은 쉽지 않습니다. 기존에 구성된 열차에 다른 차량을 끼워넣는 일은 비실용적이어서 하지 않기에, 한 차량은 오로지 열차의 전면 혹은 후미에만 추가하는 것이 가능합니다.

차량들은 미리 준비된 순서에 따라 역에 도착합니다. 에린은 각 차량이 기차역에 도착할 때, 전면 혹은 후미에 차량을 추가하거나, 차량을 열차에 추가하는 것을 거부할 수 있습니다. 에린이 최종적으로 만든 열차는 가능한 길어야(많은 차량으로 구성되어야)하지만, 그 과정에서 열차는 에린이 배열하고자하는 정렬 순서에 맞아야 합니다.

각 차량이 역에 도착하는 순서대로 차량들의 중량이 주어질 때, 에린이 만들 수 있는 가장 긴 열차배열의 길이(=차량의 수)는 얼마입니까?

입력

첫째 줄에 차량의 수를 나타내는 N (0 <= N <= 2000)이 주어집니다. 이후 N개의 각 줄에는 음이 아닌 차량의 무게가 주어집니다. (단, 서로 다른 두 차량의 무게가 같은 일은 발생하지 않습니다.)

출력

에린이 만들 수 있는 가장 긴 열차의 길이를 출력하세요.

예제 입력 1 

3
1
2
3

예제 출력 1 

3

     

 문제 풀이

1차 풀이 (  2120 KB,  84 ms)

하나를 중앙으로 고정시킨 뒤,  

그 중앙을 최댓값으로 하는 최장 증가 부분수열과,

그 중앙을 최솟값으로 하는 최장 감소 부분수열을 구한 뒤,

그 두개를 더하고 +1을 한다.

중앙값이 각 부분수열에서 제외되었기 때문.

#include <bits/stdc++.h>
using namespace std;

int N, val;
unsigned long ans=0;

int main()
{
        cin.tie(nullptr);
        ios::sync_with_stdio(false);

        vector<int> car;
        deque<int> asc, des;
        cin >> N;

        for(int i=0; i<N; i++) {
                cin >> val;
                car.push_back(val);
        }

        
        for(int i=0; i<car.size(); i++){
                int fix = car[i];
                asc.clear();
                des.clear();
                for(int j=i+1; j<car.size(); j++)
                {
                        int weight = car[j];
                        if(fix < weight) {
                                int idx = lower_bound(asc.begin(), asc.end(), weight) - asc.begin();
                                if(idx == asc.size()) asc.push_back(weight);
                                else asc[idx] = weight;
                        }
                        if(fix > weight) {
                                int idx = lower_bound(des.begin(), des.end(), weight, greater<>()) - des.begin();
                                if(idx == des.size()) des.push_back(weight);
                                else des[idx] = weight;
                        }
                }
                ans = max(ans, asc.size() + des.size() + 1);
        }
        cout << ans;
}