[Algo] 백준 가장 긴 바이토닉 부분 수열 c++ // LIS, LDS, (dp), 이분탐색

* 시도

• 완탐 : 해당 원소를 포함, 불포함 o, x로 나누어서 완탐하기
  • 2^1000 -> 불가
  • 완성된 배열에서도 바이토닉 찾기가 매우 까다로움
• dp -> n^2에 가능하나, n lgn풀이인 이분탐색으로 풀고자함.

for (int i = 0; i < n; ++i) {
    int idx = lower_bound(lis, lis + len, nums[i]) - lis;

    if (idx == len) {
        len++;
    }
    //(lis에없는)개큰수가 등장한 경우, 맨뒤에 추가해줌, lis길이+1
    //lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!!

    lis[idx] = nums[i]; //기존값을 더 작은값으로 교체
}

• lis의 len 구한후, 뒤집어서 범위제한후 len2 구하고 더하면 될듯?

last_idx로 범위제한하고, reverse해서 lis 구해서 길이 더하면 될듯?

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

ll lis[1004], lis2[1004];
ll nums[1004];
int n,len, len2;

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    int last_idx = 0;
    for (int i = 0; i < n; ++i) {
        int idx = lower_bound(lis, lis + len, nums[i]) - lis;

        if (idx == len) {
            len++;
            last_idx = i;
        }
        //(lis에없는)개큰수가 등장한 경우, 맨뒤에 추가해줌, lis길이+1
        //lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!!

        lis[idx] = nums[i]; //기존값을 더 작은값으로 교체
    }

    reverse(nums, nums + n);

    int max_idx = n - last_idx;
    //cout << "dd  "<< max_idx << " "<< last_idx;
    for (int i = 0; i < max_idx; ++i) {
        int idx = lower_bound(lis2, lis2 + len2, nums[i]) - lis2;

        if (idx == len2) {
            len2++;
        }
        //(lis에없는)개큰수가 등장한 경우, 맨뒤에 추가해줌, lis길이+1
        //lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!!

        lis2[idx] = nums[i]; //기존값을 더 작은값으로 교체
    }

    cout << len+ len2 -1 ;

    return 0;
}

반례 / 실제는 1 4 3 2 1 (5)임

 

* 수정

• 단순히 길이만으로는 최적해를 구할수없음.
• 각각의 idx에 왔을때, lis길이가 얼마인지, 각각의 상태를 기록해야함! // dp[i] = len

for (int i = 0; i < n; ++i) {
    int idx = lower_bound(lis, lis + len, nums[i]) - lis;

    if (idx == len) {
        len++;
    }
    //(lis에없는)개큰수가 등장한 경우, 맨뒤에 추가해줌, lis길이+1
    //lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!!

    lis[idx] = nums[i]; //기존값을 더 작은값으로 교체
    dp1[i] = len;
}

• 뒷부분에서 모든 상태를 탐색하면서 최대값을 찾아야함.

 

* LDS 구하는법 (n lg n)

그냥 뒤에서부터 탐색하면 된다! (음수 할필요없음)

for (int i = n-1; i >= 0; --i) {
    int idx = lower_bound(lis2, lis2 + len2, nums[i]) - lis2;

    if (idx == len2) {
        len2++;
    }
    //(lis에없는)개큰수가 등장한 경우, 맨뒤에 추가해줌, lis길이+1
    //lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!!

    lis2[idx] = nums[i]; //기존값을 더 작은값으로 교체
    dp2[i] = len2;
}

• 마지막에 모든 상태를 완탐하면서 최대값을 구하면된다.
• 겹치는 원소때문에 -1 해주기

int ret = 0;
for (int i = 0; i < n; ++i) {
    ret = max(ret, dp1[i] + dp2[i] - 1);
}

cout << ret;

dp1, dp2, 정답(두개합해서 최대값-1)

 

* 전체코드

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

int lis[1004], lis2[1004], dp1[1004], dp2[1004];
int nums[1004];
int n,len, len2;

int main()
{
    //memset(dp1, 1, sizeof(dp1));
    //memset(dp2, 1, sizeof(dp2));

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    for (int i = 0; i < n; ++i) {
        int idx = lower_bound(lis, lis + len, nums[i]) - lis;

        if (idx == len) {
            len++;
        }
        //(lis에없는)개큰수가 등장한 경우, 맨뒤에 추가해줌, lis길이+1
        //lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!!

        lis[idx] = nums[i]; //기존값을 더 작은값으로 교체
        dp1[i] = len;
    }
    for (int i = 0; i < n; ++i) {
        cout << dp1[i] << " ";
    }cout << "\n";


    for (int i = n-1; i >= 0; --i) {
        int idx = lower_bound(lis2, lis2 + len2, nums[i]) - lis2;

        if (idx == len2) {
            len2++;
        }
        //(lis에없는)개큰수가 등장한 경우, 맨뒤에 추가해줌, lis길이+1
        //lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!!

        lis2[idx] = nums[i]; //기존값을 더 작은값으로 교체
        dp2[i] = len2;
    }

    for (int i = 0; i < n; ++i) {
        cout << dp2[i] << " ";
    }cout << "\n";

    int ret = 0;
    for (int i = 0; i < n; ++i) {
        ret = max(ret, dp1[i] + dp2[i] - 1);
    }

    cout << ret;

    return 0;
}