Hi, I solved this problem with a very simple dp and it was an editorial idea too but at the end of the editorial, it mentioned that we can optimize it but I can't get how we can do this? problem link ==> https://codeforces.net/contest/711/problem/C
We compute the following array : dp[i][j][k] denoting the minimum amount of paint needed to color the first i trees such that it has beauty j and the i-th tree is colored by color k, and initialize all these values to ∞. We can compute this dp array easily by considering two cases :
When the last color used is equal to the current color, then we should compare it with dp[i - 1][j][k] + cost[i][k] if it was originally uncolored or dp[i - 1][j][k] otherwise, since the beauty of the coloring is the same.
When the last color used is different from the current color, then we should compare it with dp[i - 1][j - 1][l] + cost[i][k] or dp[i - 1][j - 1][l] for all 1 ≤ l ≤ m except when l is equal to the current color, by similar reasoning.
If the current tree is uncolored, we loop through all the m possible colors to color it.
Starts from here ==> Naively implementing this dp will give an O(nkm2), which is sufficient to pass for this problem. However, it is possible to optimize it into O(nkm) by avoiding iterating through all colors when considering the last color used and store two global minimums. See the code for more the details.
Thanks in advance :(
