Marbles CodeForces - 1215E 状态压缩dp

问题：

Monocarp has arranged nn colored marbles in a row. The color of the ii-th marble is aiai. Monocarp likes ordered things, so he wants to rearrange marbles in such a way that all marbles of the same color form a contiguos segment (and there is only one such segment for each color).

In other words, Monocarp wants to rearrange marbles so that, for every color jj, if the leftmost marble of color jj is ll-th in the row, and the rightmost marble of this color has position rr in the row, then every marble from ll to rr has color jj.

To achieve his goal, Monocarp can do the following operation any number of times: choose two neighbouring marbles, and swap them.

You have to calculate the minimum number of operations Monocarp has to perform to rearrange the marbles. Note that the order of segments of marbles having equal color does not matter, it is only required that, for every color, all the marbles of this color form exactly one contiguous segment.

Input

The first line contains one integer nn (2≤n≤4⋅105)(2≤n≤4⋅105) — the number of marbles.

The second line contains an integer sequence a1,a2,…,ana1,a2,…,an (1≤ai≤20)(1≤ai≤20), where aiai is the color of the ii-th marble.

Output

Print the minimum number of operations Monocarp has to perform to achieve his goal.

Examples

Input

7
3 4 2 3 4 2 2

Output

3

Input

5
20 1 14 10 2

Output

0

Input

13
5 5 4 4 3 5 7 6 5 4 4 6 5

Output

21

Note

In the first example three operations are enough. Firstly, Monocarp should swap the third and the fourth marbles, so the sequence of colors is [3,4,3,2,4,2,2][3,4,3,2,4,2,2]. Then Monocarp should swap the second and the third marbles, so the sequence is [3,3,4,2,4,2,2][3,3,4,2,4,2,2]. And finally, Monocarp should swap the fourth and the fifth marbles, so the sequence is [3,3,4,4,2,2,2][3,3,4,4,2,2,2].

In the second example there's no need to perform any operations.

题意：给一个数字序列（长度为4e5），数字大小为（1-20），求每次交换相邻两数字使得所有相同数字在一个线段的最小交换次数。

思路：我们用一个20位的二进制字符串表示状态，第i位为1则代表数字i全部排序完毕，我们要的答案很明显就是20个1的二进制字符串了（即1<<20-1）对于一个确定的状态i，我们已经有一个已经排好了并在前面的集合（集合里包括的数是所有i的二进制为1的颜色），之后我们就将二进制为0的放在它们的最前面，那么交换次数就是该颜色和集合内颜色逆序对总和。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a,ans[25];
long long dp[1<<20],s[25][25];
int main()
{
    long long sum;
    int n;
    scanf("%d",&n);
    memset(s,0,sizeof(s));
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a);
        for(int j=1; j<=20; j++)//这点不好想，意思是s[i][j]表示所有颜色j的珠子想要移动到最终位置需要跨过颜色i的珠子的总数 
        ans[a]++;
    }
    memset(dp,0x3f3f3f3f,sizeof(dp));
    dp[0]=0;
    for(int i=0; i<(1<<20); i++)
        for(int j=0; j<20; j++)
            if(!(i&(1<<j)))
            {
                sum=0;
                for(int k=0; k<20; k++)
                    if(i&(1<<k))//第k+1位是1，也就是说第k+1中颜色的珠子已经全部移到指定位置了 
                        sum=sum+s[k+1][j+1];
                dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+sum);
            }
    printf("%lldn",dp[(1<<20)-1]);
}

 

最后

以上就是凶狠凉面为你收集整理的Marbles CodeForces - 1215E 状态压缩dp的全部内容，希望文章能够帮你解决Marbles CodeForces - 1215E 状态压缩dp所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。