I’m not going to introduce the knowledge before we get the DP equation, which is well illustrated in the official editorial.
First, the array should be sorted in descending order, and then we will get a DP equation.
dp[i][j] = min(dp[i-1][k] + (j - k)*val_j),(k < j)
Obviously, the time complexity is O(n^2z)
Let’s see what’s hidden in this formula.
Suppose we have two unknowns m_1 and m_2, they satisfy m_1 < m_2 < j
Their contributions to the formula are as follows:
S_1=dp[i-1][m_1]+(j-m_1)*val_j
S_2=dp[i-1][m_2]+(j-m_2)*val_j
If m_1 is better than m_2, that is to say, S_1 < S_2
So dp[i-1][m_1]+(j-m_1)*val_j < dp[i-1][m_2]+(j-m_2)*val_j
It is equivalent to \frac{dp[i-1][m_1]-dp[i-1][m_2]}{m_1-m_2}>val_j
We were surprised to find out how this formula seems to be related to slope.
For convenience, Let f(x) =dp[i-1][x]
So \frac{f(m_1)-f(m_2)}{m_1-m_2}>val_j
Let’s draw a picture.
We find that m_1 is better than m_2 if the slope of straight line AB is greater than val_j , and vice versa.
Well, we seem to have found a clue to optimization.
Let’s draw all k, f(k) satisfactions (k < j). it could be like this:
Let’s tell you which point can be ignored.
If Slope(A,B)>Slope(B,C) .So this point B is a useless point. No matter how much val_j it is, point B is either inferior to point A or inferior to point C.
The proof is very simple. Let’s leave it to you to think about.
If we delete all the useless points, the image will become like this:
Amazingly, the slope of this image is increasing.
So, there must be the following:
Slope(m_1,m_2)<Slope(m_2,m_3)<...Slope(m_x,m_{x+1})<val_j<Slope(m_{x+1},m_{x+2})<...
Because Slope(m_1,m_2)<val_j,So m_2 is better than m_1, for the same reason, we can find m_{x+1} is the optimal point.
So we can use binary search to find the appropriate m_{x+1} for each val_j, so that O (nzlogn)
But we can do better. We don’t need a binary search at all, because val_j is decreasing.
So we can use a stack to maintain these points. so that O(nz)
This is my solution: CodeChef: Practical coding for everyone