Sort a permutation minimizing the total cost of moves
Разница между en4 и en5, 3 символ(ов) изменены
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 \leq N \leq 1000$, however solutions with any reasonable complexity are welcome.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский 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 Английский 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 Английский f2lk6wf90d 2017-12-30 22:49:59 2 Tiny change: 'as $i+j$ (1-indexed).' -> 'as $i+j$ ($1$-indexed).'
en3 Английский f2lk6wf90d 2017-12-30 19:43:14 5 Tiny change: '\nExample:\n`[1,3,4,' -> '\nExample: \n`[1,3,4,'
en2 Английский f2lk6wf90d 2017-12-30 16:27:07 8
en1 Английский f2lk6wf90d 2017-12-30 02:57:47 774 Initial revision (published)