| # | User | Rating |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
http://codeforces.me/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?
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.