Preprocessing for DP+Bitmask

Правка en2, от Nams, 2015-10-10 10:27:58

Hello All,

I came across this interesting question in which there is an array consisting of n numbers with each number lying between 1 to m. Now it is asked to find the minimum number of swaps necessary to reformat the array such that the array elements with same value come together.

Note: Here Here swap means exchanging position of two adjacent numbers.

Example: If N=4 && M=2 && A[4]=1 2 1 2 => Ans=1

If N=6 && M=4 && A[6]=2 1 4 3 1 2 => Ans=6

Constraints: 1<=N<=10^5 && 1<=M<=16

I have been able to find that this question can be solved using DP+bitmasking but I am facing difficulty in forming the DP structure. So if anybody can help,it will be really grateful.

Thanks

Теги dp, bitmasking

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Nams 2015-10-10 10:27:58 4
en1 Английский Nams 2015-10-10 10:26:39 728 Initial revision (published)