https://www.acmicpc.net/problem/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;
}
'BOJ' 카테고리의 다른 글
[BOJ 2042] 구간 합 구하기 (0) | 2022.01.18 |
---|---|
[BOJ 8903] 장비 (0) | 2022.01.13 |
[BOJ 23578] 비 오는 날 (0) | 2022.01.13 |
[BOJ 10523] 직선 찾기 (0) | 2022.01.11 |
[BOJ 13255] 동전 뒤집기 (0) | 2022.01.11 |