3350번: Candy Machine

https://www.acmicpc.net/problem/3350


$O(nlgn)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, r[100000], dp[100000], sz;
pair<int, int> p[100000];
int main() {
    scanf("%d", &n);
    for (int i = 0, s, t; i < n; i++) {
        scanf("%d%d", &s, &t);
        p[i] = { t - s,s + t };
    }
    sort(p, p + n);
    for (int i = n; i--;) {
        int t = lower_bound(dp, dp + sz, p[i].second) - dp;
        dp[t] = p[i].second;
        r[i] = t;
        if (t == sz) sz++;
    }
    printf("%d", sz);
    for (int i = 0; i < n; i++) printf("\n%d %d %d", (p[i].second - p[i].first) / 2, (p[i].first + p[i].second) / 2, r[i] + 1);
    return 0;
}

13711번: LCS 4

https://www.acmicpc.net/problem/13711


$O(N\lg N)$

Ai를 i로 바꿔 생각하면 LIS를 구하는 문제와 동치이다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int idx[MXN + 1], dp[MXN], n, x;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &x), idx[x] = i;
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        dp[i] = n;
        *lower_bound(dp, dp + i, idx[x]) = idx[x];
    }
    printf("%d", lower_bound(dp, dp + n, n) - dp);
    return 0;
}

2568번: 전깃줄 - 2

https://www.acmicpc.net/problem/2568


$O(n\lg n)$

한 쪽 번호를 기준으로 정렬한뒤 다른 한 쪽 번호를 이용해 최장증가수열을 구한다. 이 수열에 포함되지 않는 전깃줄을 제거한다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5, MXI = 5e5;
pair<int, int> p[MXN];
int n, sz, dp[MXN], fr[MXI + 1], ck[MXI + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].first, &p[i].second);
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        int h = lower_bound(dp, dp + sz, p[i].second) - dp;
        if (h == sz) sz++;
        dp[h] = p[i].second;
        fr[dp[h]] = h ? dp[h - 1] : 0;
    }
    printf("%d\n", n - sz);
    for (int i = dp[sz - 1]; i; i = fr[i]) ck[i] = 1;
    for (int i = 0; i < n; i++) if (!ck[p[i].second]) printf("%d\n", p[i].first);
    return 0;
}

12015번: 가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12015


$O(n\lg n)$

#include<cstdio>
#include<algorithm>
int n, a[1000000], sz, x;
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &x);
        int p = std::lower_bound(a, a + sz, x) - a;
        sz += p == sz;
        a[p] = x;
    }
    printf("%d", sz);
    return 0;
}

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

https://www.acmicpc.net/problem/12738


$O(n\lg n)$

#include<cstdio>
#include<algorithm>
int n, a[1000000], sz, x;
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &x);
        int p = std::lower_bound(a, a + sz, x) - a;
        sz += p == sz;
        a[p] = x;
    }
    printf("%d", sz);
    return 0;
}

14002번: 가장 긴 증가하는 부분 수열 4

https://www.acmicpc.net/problem/14002

$O(n\lg n)$

LIS구현

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[1001], dp[1001], idx[1001], fr[1001];
void f(int h) {
    if (!h) return;
    f(fr[h]);
    printf("%d ", a[h]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e9;
        int p = lower_bound(dp + 1, dp + 1 + i, a[i]) - dp;
        dp[p] = a[i];
        idx[p] = i;
        fr[i] = idx[p - 1];
    }
    int sz = lower_bound(dp + 1, dp + 1 + n, 1e9) - dp - 1;
    printf("%d\n", sz);
    f(idx[sz]);
    return 0;
}

11568번: 민균이의 계략

https://www.acmicpc.net/problem/11568


$O(n\lg n)$

최장증가부분수열을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[1000];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i<n; i++) {
        scanf("%d", &x);
        a[i] = 1e9;
        *lower_bound(a, a + i, x) = x;
    }
    printf("%d", lower_bound(a, a + n, 1e9) - a);
    return 0;
}

11722번: 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722


$O(n\lg n)$

수열의 각 항에 -1을 곱하고 최장증가수열을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[1000], sz, x, n;
int main() {
    for (scanf("%d", &n); n--;) {
        scanf("%d", &x);
        int p = lower_bound(dp, dp + sz, -x) - dp;
        dp[p] = -x;
        if (p == sz) sz++;
    }
    printf("%d", sz);
    return 0;
}

11054번: 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054


$O(n^2)$

dp0[i]:증가하는 도중의 최장 증가 수열 길이
dp1[i]:감소하는 도중의 최장 바이토닉 수열 길이

두 점화식을 풀어 답을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[1001], dp[2][1001], r;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        for (int j = 0; j < i; j++)
            if (a[i]>a[j]) dp[0][i] = max(dp[0][i], dp[0][j] + 1);
            else if (a[i]<a[j]) dp[1][i] = max({ dp[1][i],dp[0][j] + 1,dp[1][j] + 1 });
            r = max({ r,dp[0][i], dp[1][i] });
    }
    printf("%d", r);
    return 0;
}

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

https://www.acmicpc.net/problem/11053


$O(n^2)$

최장증가수열을 구하는 문제이다. nlgn 해법도 있다.
dp[0]=1
dp[n]= a[n]>a[i]인 i 중 max(dp[i])+1

답은 max(dp[i])

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[1001], dp[1001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        for (int j = 0; j < i; j++) dp[i] = max(dp[i], dp[j] * (a[i]>a[j]) + 1);
    }
    printf("%d", *max_element(dp, dp + 1 + n));
    return 0;
}