Yes, you’re right about the minimums, and they should in fact be everywhere (sorry, I’ll edit the comment to fix the mistakes).
To compute suf[i][j][k], use the values you already have: suf[i][j][k] = min(dp[i][j][k], suf[i][j][k + 1]). This is because in suf[i][j][k + 1] you’ve already processed dp[i][j][(k + 1) \dots M], and the only difference is the single value dp[i][j][k]. The same goes for pre, except it’s based on k - 1.
So After complete iteration of DP[i][j][i…M] we will update the suf[i][j][1…M] and pre[i][j][1…M] for the next use ??
I’m not exactly sure what you mean, but I would find it easiest to compute them after finishing all values of k for a fixed i, j pair (because you won’t need these values until you get to computing i + 1, j + 1).
Actually you just gave a green tick to my above approach…I meant exactly the same what you are saying.
Nice talking to you 
How to do the looping to find dp[i][j][k]
They extended it? What the hell? That’s the stupidest move I’ve ever seen, ofc people would talk about solutions after it ends. That being said, I’ll still remove it of course and repost it when it re-ends.
Hi @galencolin, the contest will end today can you share the solution, I tried dp but was not sure how I will find minimum value while making recursive calls as there can be n types of paints.
Tell me when the thing actually ends, I’ll just re-paste it in
(Reposted):
Denote c[i][j] to be the cost of painting the i-th building as color j. Also, assume 1-indexing for everything as it makes the math easier.
Let dp[i][j][k] be the minimum cost to paint the first i buildings with j as the specialty of the first i buildings, such that the last color used was k (as in, the color of the i-th building is k). If the color of the i-th building is fixed, then all dp[i][j][k] for that i are \infty except for when k is the fixed color. Then when computing dp[i][j][k], there are two possibilities:
The color k is the same as the previous color. Then, when placing this color, the specialty does not change. So the value of this transition is dp[i - 1][j][k] + c[i][k]. This takes O(1) time.
The color k is different from the previous color. In this case, the specialty increases by 1, so the previous specialty must be 1 less than j. So the value of this transition is the minimum value of dp[i - 1][j - 1][p] + c[i][k], where p is any valid color not equal to k. This takes O(M) time.
The answer is the minimum over dp[N][K][c] over all 1 \leq c \leq M.
Naively, there are O(NMK) states and transitions are O(M). This will probably not pass if all tests in a file are maxtests. But we can speed the second type of transition up. Let pre[i][j][k] be the prefix minimum of dp[i][j][1 \dots k], and suf[i][j][k] be the suffix minimum of dp[i][j][k \dots M]. Then the entire second transition can be computed as min(pre[i - 1][j - 1][k - 1], suf[i - 1][j - 1][k + 1]) + c[i][k] (be careful with edge cases). Now this is O(NMK), which should pass easily.