mo7amed_a7med's blog

337A How to apply dynamic programming
By mo7amed_a7med, history, 8 years ago, In English

how to solve 337A by using dp as it mentioned in its tag ?

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

You asked for DP, you will get DP.

Define f(rem,pos,min,max) to be taking rem elements from first pos elements with min as minimum and max as maximum — this function can be calculated using DP. Apply coordinate compression on values to limit min and max to O(n). Total complexity = O(n^4).

http://mirror.codeforces.com/contest/337/submission/22187455

→ Reply