구간 나누기 - KOITP_201601_INTERVALDIVISION
문제 링크(koitp.org/problem/KOITP_201601_INTERVALDIVISION/)동적계획법으로 해결할 수 있다.dp(k, i) : i번째 수까지 k개의 구간을 정했을 때의 최적해dp(k, i) = max[dp(k-1, j) + max(A(j+1)~A(i)) - min(A(j+1)-A(i))]여기서 max( )와 min( )을 계산하는데 O(N)이 걸려서 한 가지 변형을 한다.dp_contain_max(k, i) = max[dp(k-1, j) + max(A(j+1)~A(i))]dp_contain_min(k, i) = max[dp(k-1, j) - min(A(j+1)~A(i))]그러면 dp(k, i) = max[dp_contain_max(k, i) - A(i), dp_contain_min(..
2017. 1. 22.
