BOJ 14181 - 함수와 쿼리 (D3)
CHT 처음 배울때 봤다가 이게 왜 CHT지 하고 탈주했다. http://boj.kr/14181 14181번: 함수와 쿼리 첫째 줄에 배열 a의 크기 n (1 ≤ n ≤ 105)가 주어지고, 둘째 줄에 배열 a[1], a[2], ..., a[n]이 주어진다. (0 ≤ a[i] ≤ 104) 다음 줄에는 쿼리의 개수 m (1 ≤ m ≤ 105)가 주어지고, 다음 m개의 줄에는 쿼리 www.acmicpc.net 풀이) Li-chao + Segment Tree 점화식을 세우기 영 쉽지 않아 보인다. 그러므로 정의에 따라 점화식을 관찰하자. $$ f(1,j)=a[j] $$ $$ f(2,j) = min (f(1,j), f(1,j-1)) + a[j] $$ $$ = min(2*a[j], a[j-1] + a[j]) $$..
더보기