dnc_opt

f(i,j)=min{k<j}{f(i-1,k)+cost(j,k)} 뭐 이런식으로 많이 표현하지만, 사실 더 일반적으로 강력하게 사용할 수 있는듯 하다. 18799번을 풀다보니 f(i-1,k)가 아니라 f(k,i-1)형태로 조금 꼬여있었는데, k=opt[i]의 단조성이 존재하면 그 f(i,j)를 구하면 f(i,j0<j)의 범위와 f(i,j1>j)의 범위를 나누어 분할정복이 가능하다. 저 문제는 그 k_opt의 단조성조차 없는데, lcp단조성으로 어떻게 잘 한다는듯. 저게 어떻게 다이아5인지 모르겠다.

Monotone Opt의 경우 opt단조성만으로는 부족하고, value의 교차점이 하나라는 더 강력한 조건이 필요해서 가능하면 DnC최적화 먼저 생각해보는게 좋겠다.