POI 18회 스테이지3 문제2. Monotonicity 2
문제 설명 https://www.acmicpc.net/problem/8195 풀이 * 아래 풀이는 POI 공식 사이트에서 볼 수 있는 풀이(폴란드어로 쓰여 있음)를 참조했습니다. (https://oi.edu.pl/) 1. 개요 우리가 해결할 문제는, 주어진 수열 \(a_1, a_2, \dots, a_n\)의 부분수열 \(a_{b_1}, a_{b_2}, \dots, a_{b_k}\) 중, 모든 \(1 \le i \le n-1\)에 대해 \(i\)번째 항과 \(i+1\)번째 항 사이에 \(a_{b_i} \,\langle s_i \rangle\, a_{b_{i+1}}\)이 성립하는 것 중 가장 긴 것을 찾는 것이다. 여기서 \(\langle s_i \rangle \)는 부등호 또는 등호인 \(s_i\)를 \(..
더보기