LIS (Longest Increasing Subsequence)

DP의 대표적인 문제중 하나이다.

O(N^2)

2565번: 전깃줄

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>

#define arr(i) cable[i].second

using namespace std;

typedef long long LL;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

int n, a, b;

int dp[104];

void solve() {
    cin >> n;
    vii cable(n);

    for (auto& c : cable) {
        cin >> a >> b;
        c = {a, b};
    }

    sort(cable.begin(), cable.end());

    **// LIS
    int lis = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr(j) < arr(i)) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        lis = max(lis, dp[i]);
    }**
    cout << n - lis << '\\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
}

O(N log N)

12738번: 가장 긴 증가하는 부분 수열 3

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

int arr[1000001];
vi sr;

void solve() {
    int t;

    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> arr[i];
    }
    sr.push_back(arr[0]);
    for (int i = 1; i < t; i++) {
        if (sr.back() < arr[i])
            sr.push_back(arr[i]);
        else {
            *lower_bound(sr.begin(), sr.end(), arr[i]) = arr[i];
        }
    }
    cout << sr.size() << '\\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
}

O(N log N) + Backtracking

추적방법

예제 : 2568 전깃줄-2

2568번: 전깃줄 - 2

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define arr(i) arr[i].second

int n, ans;
int a, b;
vii arr;    // 원본 수열
vi lis;     // 실제 LIS
vi dp;      // NlogN 을 위한 임시 LIS
vi record;  // 현재 입력되는 수가 임시 LIS배열의 몇번째 idx인가?

bool cut[100001];

void solve() {
    cin >> n;
    arr.resize(n);
    record.resize(n);

    for (auto& i : arr) {
        cin >> a >> b;
        i = {a, b};
    }

    sort(arr.begin(), arr.end());

    dp.push_back(arr(0));
    //

    for (int i = 1; i < n; i++) {
        if (dp.back() < arr(i)) {
            record[i] = dp.size();
            dp.push_back(arr(i));
        } else {
            auto it = lower_bound(dp.begin(), dp.end(), arr(i));
            *it = arr(i);
            record[i] = it - dp.begin();
        }
        ans = max(ans, (int)dp.size());
    }

    cout << n - ans << '\\n';

    for (int i = n - 1,
             j = dp.size() - 1;
         i >= 0; i--) {
        if (record[i] == j) {
            j--;
            cut[i] = true;
        }
    }
    for (int i = 0; i < n; i++) {
        if (cut[i]) continue;
        cout << arr[i].first << '\\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
}

예제 : 14003 가장 긴 증가하는 부분 수열 5

14003번: 가장 긴 증가하는 부분 수열 5

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

int n;
vi arr;

vi dp;
vi record;
vi lis;

void solve() {
    cin >> n;
    arr.resize(n);
    record.resize(n);

    for (auto& i : arr) {
        cin >> i;
    }

    dp.push_back(arr[0]);
    for (int i = 1; i < n; i++) {
        if (dp.back() < arr[i]) {
            record[i] = dp.size();
            dp.push_back(arr[i]);
        } else {
            auto it = lower_bound(dp.begin(), dp.end(), arr[i]);
            *it = arr[i];
            record[i] = it - dp.begin();
        }
    }

    cout << dp.size() << '\\n';

    for (int i = n - 1,
             j = dp.size() - 1;
         i >= 0; i--) {
        if (record[i] == j) {
            j--;
            lis.push_back(arr[i]);
        }
    }
    reverse(lis.begin(), lis.end());

    for (int i : lis) {
        cout << i << '\\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
}