R620(Div.2) D. Shortest and Longest LIS

 

대회 때 1시간동안 못풀고 끝난 문제다~~!

그리디 처럼 생각했는데 결국 떠오르지가 않는다

그리디와 수학 연습을 해야한다는걸 코포 할 때마다 느끼게된다

 

먼저 이 문제를 어떻게 접근해야할까

 

내가 가장 큰 LIS를 찾는다고 생각하면 그건 <의 수에 의존하게된다

<이 나타날때마다 작은수를 차례대로 넣어주면 <의 수 +1만큼이 최대가 될 것이다

 

작은경우도 비슷하게 생각하면 연속적인 <의 수 1이 될것이다!!

(맞나 기억이 잘 안난다..!)

 

그래서 이제 큰 경우를 찾아보자

큰 LIS를 찾을 때는 <을 찾을때마다 앞에 작은수를 채우면 된다

연속적인 <에서 맨 뒤는 빈 자리로 남겨둔다

 

왜냐면 다음 >을 채울 때 채워야하기 때문에!

<을 다 채운 다음에는 큰 수부터 >을 채우면 된다

 

작은경우는 반대로 하면 된다

 

조금 더럽게풀어서 소스가 좀 더럽다...!

 

근데 이런 문제를 풀 때는 경우를 정리하면서 

언제가 확실히 최적이 되는지 좀 손으로 써가며 정리를 해야겠다

 

소스코드

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int maxarr[MAXN], minarr[MAXN];
string s;
int n;
 
int main() {
    int t; scanf(" %d", &t);
    while (t--) {
        scanf(" %d", &n);
        cin >> s;
        memset(maxarr, 0, sizeof(maxarr));
        memset(minarr, 0, sizeof(minarr));
        int num = 1;
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == '<') {
                int j = i;
                while (s[j] == '<' && i <= n - 1)j++;
                for (int k = i; k < j; k++) maxarr[k] = num++;
                i = j - 1;
            }
        }
        num = n;
        for (int i = 0; i < n; i++) if (!maxarr[i]) maxarr[i] = num--;
 
 
        num = n;
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == '>') {
                int j = i;
                while (s[j] == '>' && j < n - 1) j++;
                for (int k = i; k < j; k++) minarr[k] = num--;
                if (j == n - 1) minarr[j] = 1;
                i = j - 1;
            }
        }
 
        for (int i = 0; i < n - 1; i++) {
            if (!minarr[i]) {
                int j = i;
                while (!minarr[j] && j <= n - 1) j++;
                for (int k = i; k < j; k++) minarr[k] = num--;
                reverse(minarr + i, minarr + j);
            }
        }
        for (int i = 0; i < n; i++) printf("%d ", minarr[i]); puts("");
        for (int i = 0; i < n; i++) printf("%d ", maxarr[i]); puts("");
    }
}