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

Spoj problem lsort(dynamic programming)
Автор codolove, история, 9 лет назад, По-английски

I am trying to solve this on spoj. I have first precomputed the index for both the case(appending number to beginning and appending number to end). Then, I used top down approach to find the minimum value. It works on most test cases but gives wrong answer on spoj. I am not able to figure out the reason. Please help. My Soloution

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Your target is value of f(a, 1, n, n, n). And approach reversed than in code, for dp[x][y] you need f(v,min(x,y)+1,y,n,level-1) and f(v,x,max(x,y)-1,n,level-1). Recursive base is if (x == y) return dx[x][x] (or dy[x][x]).

→ Ответить