Booksort 启发式函数很重要h(s1)<=h(s2)+cost(s1,s2);

  1 /*
  2 其中启发式函数要满足三角不等式h(s1)<=h(s2)+cost(s1,s2);
  3 
  4 */
  5 #include<iostream>
  6 #include<string>
  7 #include<cstring>
  8 #include<cstdio>
  9 #include<cmath>
 10 using namespace std;
 11 int n,book[30];
 12 //int i,j,k;
 13 bool flag;
 14 int lim;
 15 bool isok()
 16 {
 17   int i,j,k;
 18   for(i=1;i<=n;i++)
 19    if(book[i]!=i)
 20     return false;
 21   return true;
 22 }
 23 int h()//启发式函数
 24 {
 25     int ret=0;
 26     int i;
 27     if(book[1]!=1)
 28       ret++;
 29     if(book[n]!=n)
 30       ret++;
 31     for(i=2;i<n;i++)
 32      if(book[i]+1!=book[i+1])
 33         ret++;
 34     return ret;
 35 }
 36 void put(int st,int len,int pos)//数组的移动
 37 {
 38     int tmp[30];
 39     int it,jt;
 40     for(it=1;it<=len;it++)
 41      tmp[it]=book[st+it-1];
 42     if(pos>st)
 43     {
 44       for(it=st+len;it<=pos;it++)
 45         book[it-len]=book[it];
 46       for(it-=len,jt=1;it<=pos;it++,jt++)
 47         book[it]=tmp[jt];
 48     }
 49     else
 50     {
 51         for(it=st-1;it>pos;it--)
 52          book[it+len]=book[it];
 53         for(it=1;it<=len;it++)
 54          book[it+pos]=tmp[it];
 55     }
 56 }
 57 void dfs(int dp)
 58 {
 59     if(flag)
 60        return;
 61     if(dp*3+h()>lim*3)//如果不满足条件，则剪枝返回
 62       return;
 63     if(isok())
 64     {
 65         flag=true;
 66         return;
 67     }
 68     int i,j,k;
 69     int tmp[30];
 70     for(i=1;i<=n;i++)
 71      tmp[i]=book[i];
 72     for(i=1;i<n;i++)
 73     {
 74         for(j=1;i+j<=n+1;j++)
 75         {
 76             for(k=0;k<=n;k++)
 77             {
 78                 if(j<=k&&i+j<k)
 79                  continue;
 80                 put(j,i,k);
 81                 dfs(dp+1);
 82                 for(int tt=1;tt<=n;tt++)//还原
 83                  book[tt]=tmp[tt];
 84             }
 85         }
 86     }
 87 
 88 }
 89 int main()
 90 {
 91   int i,j,k,cas;
 92   scanf("%d",&cas);
 93   while(cas--)
 94   {
 95       scanf("%d",&n);
 96       lim=0;
 97       for(i=1;i<=n;i++)
 98        {
 99            scanf("%d",&book[i]);
100            if(book[i]==i)
101             lim++;
102        }
103        if(lim==n)
104        {
105            printf("0\n");
106            continue;
107        }
108        lim=1;
109        flag=false;
110        while(1)
111        {
112            dfs(0);
113            if(flag)
114             break;
115            lim++;
116            if(lim>4||flag)
117              break;
118 
119        }
120        if(flag)
121         printf("%d\n",lim);
122        else
123         printf("5 or more\n");
124     }
125     return 0;
126 }