CSP2019 Day2T2 분할 최적화
기본적인 동적계획법 접근은 dp[i][j]를 마지막 분할 지점이 i, 이전 분할 지점이 j일 때의 최소 비용으로 정의한다. 누적합을 sum[i] = Σk=1i a[k]로 두면, 전이식은 다음과 같다:
dp[i][j] = min{ dp[j][k] + (sum[i] - sum[j])² }
( sum[i] - sum[j] ≥ sum[j] - sum[k] )
조건를 정리하면 sum[k] ≥ 2×sum[j] - sum[i]가 되며, 고정된 j에 대해 i가 증가함에 따라 하한 ...
7월 7일 02:24에 게시됨