http://codeforces.com/contest/337/problem/A

There are three tags for this problem( Greedy, Graph matching, dp). I have solved it using a greedy technique. Please help me to solve it using dp. Thanks, advanced!!!

N:B You can also suggest the graph matching solution.

The tutorial itself is a dp approach, isn't it?

Editorial is given on greedy approach.

Noob here ..

I think the problem is simple and a sort followed by a pass over every k-consicutive elements will give you an

`O(nlogn + n)`

solution which is enough for the small input sizeWhy are you trying to find a more complicated solution?

I already solved it but I am practicing DP and trying to solve this one using dp

If you want to practice DP, I suggest finding other problems where the desired approach involves DP, instead of overcomplicating a simple greedy problem.

You can make a dp(i, k, mnm, mxm). i is the index of the puzzle "you are currently at", k is the remaining number of puzzles you need to take, mnm is the index of the smallest puzzle you took so far, and mxm is the index of the largest one. The value of the dp() is the minimum difference you can achieve, from this state.

When (i == n + 1) && (k = 0), dp() is equal to (mxm — mnm). Other "ending states" are equal to infinity.

To calculate a single state of dp(), you just need to choose either to "take" or "not to take" the current element. If you take it, your dp(i, k, mnm, mxm) is equal to dp(i + 1, k — 1, new_mnm, new_mxm), where new_mnm = i, if f[mnm] > f[i], and similarly new_mxm = i, if f[mxm] < f[i]. The second case is, if you don't take the element: then dp(i, k, mnm, mxm) will be equal to dp(i + 1, k, mnm, mxm).

You get the solution by calling dp(1, m, 0, 0), where (mnm == 0) or (mxm == 0) means that you have not yet taken any puzzles. The complexity is O(n^4), and it has a low constant.

Thanks a lot...bro..