codolove's blog

Spoj problem lsort(dynamic programming)
By codolove, history, 9 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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]).

→ Reply