Divide & Conquer Optimization in DP
동적계획법에서의 분할정복 최적화 기법에 대해서 글을 써보려고 한다. 일반적으로 j E1) return; int M = (L1 + R1) / 2; ll res = 0; for (int i = max(S1, M - D); i res) res = T[M] * (M - i) + V[i], opt[M] = i; if (answer < res) answer = res; f(L1, M - 1, S1, opt[M]); f(M + 1, R1, opt[M], E1); } int main() { scanf("%d%d", &N, &D); for (int i = 1; i
2016. 6. 12.
