PA

【题目描述】

汉诺塔升级了：现在我们有?个圆盘和?个柱子，每个圆盘大小都不一样，

大的圆盘不能放在小的圆盘上面，?个柱子从左到右排成一排。每次你可以将一

个柱子上的最上面的圆盘移动到右边或者左边的柱子上（如果移动之后是合法的

话）。现在告诉你初始时的状态，你希望用最少的步数将第?大的盘子移动到第?根

柱子上，问最小步数。

【输入格式】

第一行一个正整数?，代表询问的组数。

接下来?组数据，每组数据第一行一个整数?。

接下来一行每行?个正整数，代表每个柱子上圆盘的大小。

【输出格式】

输出共?行，代表每次的答案。如果方案不存在，输出“−1” 。

【样例输入】

2 1 3

7 8

10000 1000

97 96 95

【样例输出】

-1

【样例解释】

无。

【数据范围与规定】

对于70%的数据，N的值都是相等的。

对于100%的数据，1 ≤ T ≤ 6 × 10^3 ,1 ≤ N ≤ 7。

/*
  这个题改了n个小时了，最后还是看的题解……
  刚开始从初始状态向目标状态找的，30分，TLE
  后来又从目标状态向初始状态找，把每种情况的步数走记下来，查询就简单了，结果全TLE了，看的题解，原来是我的每个状态记得东西太多了，导致常数太大，其实只要记录每个数在哪个位置，还有每个位置的顶部是哪个数就好了。 
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define M 10000000
using namespace std;
int n,top[10],pos[10],res[M],q[M],bit[10],head,tail,w[10],num[10];
bool use[M];
bool cmp(int a,int b)
{
    return w[a]<w[b];
}
void work(int s)
{
    int x=0;
    int ss=s;
    for(int a=1;a<=7;a++)
      top[a]=0;
    while(ss)
    {
        x++;
        pos[x]=ss%10;
        ss/=10;
    }
    reverse(pos+1,pos+x+1);//倒置 
    for(int a=x;a>=1;a--)
      top[pos[a]]=a;
    for(int a=1;a<=x;a++)
      if(a==top[pos[a]])
      {
        int p=pos[a];
        if (p!=1&&(a<top[p-1]||!top[p-1]))
        {
            int news=s-bit[x-a];
            if(!use[news])
            {
                q[++tail]=news;
                use[news]=true;
                res[news]=res[s]+1;
            }
        }
        if(p!=x&&(a<top[p+1]||!top[p+1]))
        {
            int news=s+bit[x-a];
            if(!use[news])
            {
                q[++tail]=news;
                use[news]=true;
                res[news]=res[s]+1;
            }
        }
      }
}

int main()
{
    //freopen("huakai.in","r",stdin);
    //freopen("huakai.out","w",stdout);
    head=1,tail=0;
    int status=0;
    bit[0]=1;
    for (int i=1;i<=7;i++)
    {
        bit[i]=bit[i-1]*10;
        status=status*10+i;
        q[++tail]=status;
        use[status]=true;
    }
    while(head<=tail)
    {
        int s=q[head++];
        work(s);
    }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
          scanf("%d",&w[i]),num[i]=i;
        sort(num+1,num+n+1,cmp);
        int s=0;
        for (int i=1;i<=n;i++)
            s=s*10+num[i];
        if (!use[s]) printf("-1
");
        else printf("%d
",res[s]);
    }
    return 0;
}

View Code