분할정복2 BOJ 15977 - 조화로운 행렬 (분할정복, 세그트리) https://www.acmicpc.net/problem/15977 정해는 다차원 세그트리나 이분탐색+set이다. https://codeforces.com/blog/entry/43319 koosaga님의 아이디어를 구현. m=2인 경우 정렬 후 LIS m=3인 경우 정렬 후 LIS on pair (x,y값이 모두 증가하는 형태) 링크의 설명이 너무 명료하므로 큰 그림은 생략. [m+1,e] 범위의 dp를 [s,m] 범위의 dp 값으로 초기화 하는 과정만 기록 세그트리는 y를 인덱스로 하고 dp값을 값으로 갖는다. 1. 하나의 벡터에 {x,y,idx}를 [s,e]범위 모두 넣어준 후 x값 기준으로 정렬한다. 2. idx가 md이하인 경우 세그트리를 업데이트 해준다. 3. idx가 md초과인 경우 세그트리의.. 2020. 5. 30. BOJ 10167 - 금광 (세그트리, 분할정복) https://www.acmicpc.net/problem/10167 현장에서 100%받은 학생이 없었다는 문제 https://www.youtube.com/watch?v=NHf7v-_azYs&list=PLN3yisVKGPfh_sdb_pxGMP3lTF91DOgOr&index=31 위 영상 참고했습니다. www.acmicpc.net/problem/17975 유사문제 좌표평면 위에 최대 3000개의 정점이 주어진다. 각 정점마다 cost가 주어진다. 어떤 직사각형 안에 담을 수 있는 cost합의 최대를 구하라 1. 좌표압축을 해도 문제의 통일성을 해치지 않는다. 좌표값을 10의 9승에서 10의 3승정도로 줄일 수 있다. 2. 직사각형의 좌하단 꼭지점을 (x1,y1), 우상단 꼭지점을 (x2,y2)라고 뒀을 때 .. 2020. 5. 11. 이전 1 다음
