Description

战神阿瑞斯听说2008年在中华大地上，将举行一届规模盛大的奥林匹克运动会，心中顿觉异常兴奋，他想让天马在广阔的天空上，举行一场精彩的天马队列变换表演。首先，战神安排n头高度不同的天马，排成一列。然后重复下面的变换：让中间的天马出列，然后该匹天马可以排在对首，也可以排在队尾，这样称为一次变换，直到出现这一列天马按从低到高的顺序排列为止。那么从初始状态到目标状态最少需要多少次变换呢？你能给战神阿瑞斯参谋参谋吗？

Input

输入文件horse.in中有两行，第一行只有一个整数n，表示天马数。

第二行有n个正整数，分别表示n匹天马的高度，每两个数字中间用一个空格分隔。

Output

输出文件horse.out只有一行，该行只有一个正整数，表示从初始状态到目标状态最少需要的变换次数。如果无论如何变换都不能得到从低到高的排列，则输出已行“No Answer”（不包括引号）。

Data Constraint

100%的数据：n只取3、5、7、9四个数字中的一个，且天马的高度为160-190之间的整数。

Solution

比赛的时候我正解数组开小了。。。我吐了

这道题主要是bfs再剪枝就能过了

考虑用一个字符串/字符数组维护操作得到的状态，以此来去重。剪掉重复广搜的情况后直接暴力广搜就行了

Code

#include <cstdio>

#include <iostream>

#include <map>

using namespace std;

int n,i,j,k,x,a[1001];

char s[1001],m[1001],f[1000001][21];

map < string , int > d;

int main()

{

    scanf("%d",&n);

    for (i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

        s[i]=i+48;

        m[i]=s[i];

    }

    for (i=1;i<=n;i++)

    {

        for (j=i+1;j<=n;j++)

        {

            if (a[i]>a[j]) swap(s[i],s[j]),swap(a[i],a[j]);

        }

    }

    for (i=1;i<=n;i++)

        f[1][i]=m[i];

    i=0;j=1;d[m+1]=1;

    while (i<j)

    {

        i++;

        for (k=1;k<=n;k++)

            m[k]=f[i][k];

        x=d[m+1];

        for (k=1;k<=n/2;k++)

            swap(m[k],m[n/2+1]);

        if (!d[m+1])

        {

            d[m+1]=x+1;

            ++j;

            for (k=1;k<=n;k++)

                f[j][k]=m[k];

            for (k=1;k<=n;k++)

        	{

            	if (m[k]!=s[k]) break;

        	}

        	if (k>n)

       		{

            	printf("%d",d[m+1]-1);

            	return 0;

        	}

        }

        for (k=1;k<=n;k++)

            m[k]=f[i][k];

        for (k=n;k>n/2+1;k--)

            swap(m[k],m[n/2+1]);

        if (!d[m+1])

        {

            d[m+1]=x+1;

            ++j;

            for (k=1;k<=n;k++)

                f[j][k]=m[k];

            for (k=1;k<=n;k++)

        	{

            	if (m[k]!=s[k]) break;

        	}

        	if (k>n)

        	{

            	printf("%d",d[m+1]-1);

            	return 0;

        	}

        }

    }

    printf("No Answer");

}

巴特西

JZOJ1496 页