### notred's blog

By notred, history, 13 months ago, You are given a permutation of the n numbers 0, 1, 2, ...., n-1. It is required to sort the permutation in increasing order. The only operation allowed on the permutation is to swap the ith element with the jth element, for any 0 <= i < j < n. Each number i has an associated weight w_i, which is a positive integer. You are also given n-1 positive integers d_0, d_1, .., d_{n-2}, where d_i is the "distance" between the ith and (i+1)th element in the sequence. The distance between the ith and jth element, d_{ij} for i < j, is defined to be d_i + d_{i+1} + ... + d_{j-1}.

The cost of swapping the ith element with the jth element is d_{ij} multiplied by the sum of weights of the two numbers that are swapped. Basically, it is the distance by which the objects are moved multiplied by their weights. In such a swap both the ith and jth element are moved by a distance d_{ij}, other elements remain where they were.

You have to find the minimum total cost of swaps required to arrange the permutation in increasing order. Any help would be appreciated.. Comments (0)