본문 바로가기

Lis4

BOJ 2532 - 먹이사슬 (LIS) https://www.acmicpc.net/problem/2532 각 요소마다 구간이 주어질 때, 어떤 구간이 한 구간을 완전 감쌀 수 있다면 먹이사슬 상 상하관계가 나뉜다고 한다. 가장 긴 먹이사슬의 크기를 구하라 priority queue를 이용해서 풀고자 했지만 잘 보이지 않는다. 2차원 평면에 그래프를 그려보면 형태가 눈에 보일 것. x값 증가, y값 감소하도록 {x,y}를 정렬한다면 y값들만 봤을 때 가장 긴 최장단조감소부분수열의 길이를 구하면된다. lower_bound대신 upper_bound를 쓰면 된다. (같은 구간은 빼주고 생각해야 함에 주의) int n; vector a; int main() { FAST; cin >> n; for (int i = 0,x,y,z; i < n; i++) {.. 2020. 5. 20.
BOJ 2568 - 전깃줄2 ( LIS, segtree ) www.acmicpc.net/problem/2568 pair로 입력받아 정렬후 second값의 LIS를 제외한 나머지의 first값 출력 위 점화식을 구간최대 세그트리를 이용해서 구하면 된다. 세그트리의 인덱스는 second값. const int MAX = 1e5 + 4; const int SMAX = (1 1) { i /= 2; seg[i] = max(seg[i * 2], seg[i * 2 + 1]); } } P val(int s, int e, int node, int ns, int ne) { if (e x >> y; a[i] = { x,y }; } sort(a + 1, a + n +.. 2020. 5. 14.
Segment Tree, LIS https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 합을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 www.acmicpc.net 가장 기본문제. 구간의 합,최댓값,최소값 등, 원소간 결합,교환법칙이 성립하는 연산에대해 구간의 연산을 구할 수 있는 알고리즘. .. 2019. 8. 18.
BOJ 3745 - 오름세 https://www.acmicpc.net/problem/3745 3745번: 오름세 문제 주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다. 정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다. n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1 < pi2 < ... < pik (i1 < i2 < ... ik)을 말한다. n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오. 입력 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케 www.acmicpc.net 가장 긴 증가하는 부분수열의 길이(LIS)를 출력하는 문제다. dp로 O(n^2) 수행시간에 해결하는 것은 종만북에서 해본 기억이 있지만,.. 2019. 8. 6.

티스토리툴바