Consider the following problem:

There are N cells in a row, each of which must be colored with a color C_i. In one step, you can choose to color any subarray of the N cells with their corresponding colors, but this has a cost equivalent to (number of distinct colors in that subarray)^2. Find the minimum cost to color all N cells.

I was able to quickly think of a simple O(N^2) DP solution: Let dp[n] = the cost to color cells 0 to n. Then, dp[n] transitions from all dp[<n]; O(N) transitions for O(N) states.

However, in this problem, N <= 50,000 (and C_i also <= 50000, but I'm not sure why this matters). This combined with the fact that the cost function is the square of the number of distinct colors makes me think that there is some sort of sqrt-bash solution. Also, dp[n] is monotonically increasing, but I'm not sure how this helps...

Can anyone provide some hints/a solution to this problem?