mo7amed_a7med's blog

By mo7amed_a7med, history, 7 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

| Write comment?
»
7 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://codeforces.com/contest/337/submission/22187455