백준14459 소가 길을 건너간 이유 11

작성일 | In

문제 링크

  • http://icpc.me/14459

문제 출처

  • 2017 Feb USACO Platinum 2번

사용 알고리즘

  • LIS

시간복잡도

  • $O(N \log N)$

풀이

약 9N개의 선분 중 몇 개만 적절히 배치해서 서로 교차하지 않도록 만들어야 합니다.
이런 문제는 LIS로 해결할 수 있다는 것이 널리 알려져 있기 때문에 선분들을 잘 정렬해서 LIS를 돌려주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 14459 소가 길을 건너간 이유 11

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int n;
int a[101010], b[101010];
vector<p> v;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        int t; cin >> t; a[t] = i;
    }
    for(int i=1; i<=n; i++){
        int t; cin >> t; b[t] = i;
    }
    for(int i=1; i<=n; i++) for(int j=-4; j<=4; j++){
            if(1 <= i+j && i+j <= n) v.emplace_back(a[i], b[i+j]);
        }
    sort(all(v), [](p a, p b){
        if(a.x != b.x) return a.x < b.x;
        return a.y > b.y;
    });
    vector<int> lis(1, -1); int ans = 0;
    for(auto i : v){
        if(lis.back() < i.y){
            ans++; lis.push_back(i.y); continue;
        }
        auto it = lower_bound(all(lis), i.y);
        *it = i.y;
    }
    cout << ans;
}