Codeforces 321E Ciel and Gondola - The DP

$dp[g][i]$ = minimum cost to assign first $i$ people to first $g$ gondolas. Transition: $dp[g][i] = \min_{j < i}(dp[g-1][j] + cost(j+1, i))$ Here $cost(l, r)$ = number of knowing pairs in $[l, r]$. Precompute with $2$D (two-dimensional) prefix sums. Naive: $O(k \cdot n^2)$.

With D&C: $O(k \cdot n \log n)$. Work through examples by hand before coding. Understanding the pattern makes implementation simple. Practice with similar problems to reinforce your understanding.