[BOJ 16474] 이상한 전깃줄

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

16474번: 이상한 전깃줄

Tag : lis

 

문제요약

전깃줄의 연결 상태가 입력으로 들어오는데 이 때 전깃줄을 최소한으로 끊어서 전깃줄이 교차하지 않는 상태를 만드는 것이 목표이다.

전깃줄을 끊는 최소 횟수를 구하라.

 

풀이

입력을 조금만 손보면 \(O(N^2)\) lis 문제가 된다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int n, m, k;
int dp[2020];
vector<int> v[2020];

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
template<typename T>
struct FASTIO {
    char *p,O[2000000],*d;
    void set() {
        struct stat st;fstat(0, &st);d=O;
        p=(char*)mmap(0,st.st_size,1,1,0,0);
    }
    ~FASTIO() {
        write(1,O,d-O);
    }
    inline T get() {
        T x=0;bool e;p+=e=*p=='-';
        for(char c=*p++;c&16;x=10*x+(c&15),c=*p++);
        return e?-x:x;
    }
    inline void put(int x) {
        if(x<0) *d++='-', x=-x;
        char t[16],*q=t;
        do *q++=x%10|48; while(x/=10);
        do *d++=*--q; while(q!=t);
        *d++=10;
    }
};

FASTIO<int> IO;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);

    IO.set();
    n = IO.get(); m = IO.get();
    map<int, int> a;
    for(int i=1; i<=n; i++) {
        int x = IO.get();
        a[x] = i;
    }
    map<int, int> b;
    for(int i=1; i<=m; i++) {
        int x = IO.get();
        b[x] = i;
    }
    k = IO.get();
    for(int i=0; i<k; i++) {
        int p = IO.get(), q = IO.get();
        v[a[p]].emplace_back(b[q]);
    }
    for(int i=1; i<=n; i++) {
        sort(v[i].begin(), v[i].end());
        v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
    }
    for(int i=1; i<=n; i++) {
        int mx = 0, e = 0;
        vector<pair<int, int>> t;
        for(auto &j : v[i]) {
            while(e + 1 < j) {
                mx = max(mx, dp[e]);
                e++;
            }
            mx = max(mx, dp[e]);
            t.push_back({j, mx + 1});
        }
        for(auto &[i, j] : t) dp[i] = max(dp[i], j);
    }
    int ans = 0;
    for(int i=1; i<=m; i++) ans = max(ans, dp[i]);
    cout << k - ans << endl;
}