Блог пользователя mo7amed_a7med

Автор mo7amed_a7med, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

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.me/contest/337/submission/22187455