Sort a permutation minimizing the total cost of moves

Revision en2, by f2lk6wf90d, 2017-12-30 16:27:07

Hello everyone, I found this problem a while ago and I'm still stuck on it (there's no OJ to submit it as far as I know):
You are given a permutation of the integers from 1 to N. In this case, moving an element from i to j is defined as removing the element from position i, and inserting it at position j. For example, in this array: [4,5,2,1,3], moving the element from 2 to 5 gives us the array [4,2,1,3,5]. The cost of moving an element from i to j is defined as i + j (1-indexed). What is the minimum total cost needed to sort the permutation?
Example: [1,3,4,5,2] -> [1,2,3,4,5] with total cost 5 + 2 = 7.
1 ≤ N ≤ 1000, however solutions with any reasonable complexity are welcome.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English f2lk6wf90d 2017-12-31 08:38:56 4 Tiny change: 'ment from 2 to 5 gives us ' -> 'ment from $2$ to $5$ gives us '
en5 English f2lk6wf90d 2017-12-31 01:35:00 3 Tiny change: '3,4,5,2]` -> `[1,2,3,4' -> '3,4,5,2]` → `[1,2,3,4'
en4 English f2lk6wf90d 2017-12-30 22:49:59 2 Tiny change: 'as $i+j$ (1-indexed).' -> 'as $i+j$ ($1$-indexed).'
en3 English f2lk6wf90d 2017-12-30 19:43:14 5 Tiny change: '\nExample:\n`[1,3,4,' -> '\nExample: \n`[1,3,4,'
en2 English f2lk6wf90d 2017-12-30 16:27:07 8
en1 English f2lk6wf90d 2017-12-30 02:57:47 774 Initial revision (published)