Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### zoro2000's blog

By zoro2000, history, 10 days ago, Question: Given an array of N elements We want to divide this into K subarrays ( non-intersecting) such that the total cost is minimum , total cost is sum of cost of all subarrays

Now for a subarray the cost is defined as the no of unordered pairs of elements which have different indices and their values are the same , i.e for array A , i < j && A[i] = A[j]

We want to output the total cost .

Constraints .

2 <= N <= 1e5 .

1 <= A[i] <= N .

2 <= K <= min(N,20) .

Eg : [ 1 , 1 , 2 , 2 , 1 ] and k = 2

Most optimal way is [ 1, 1, 2 ] [2,1] where the cost of subarray one is 1 , subarray 2 is 0

So total cost = 1 + 0 = 1

My Approach .

Seeing the constraints I tried applying a DP of index , k however I was soon faced in a issue where I needed to find the (no.of pairs for a given range l , r) in such a way that it does not exceed the time limit

How to approach such questions

PS : Thank you in advance :) dp, Comments (4)
 » Can you give the link to this problem ?
•  » » There no link to this question
 » Approach (Recursive DP)f(i, j) -> minimum cost to divide first i elements into j groups.f(i, j) = min(f(i + 1, j), f(i + 1, j + 1) + cost[j]) ;
•  » » I did not get it exactly can you please tell me more