序列（搜索剪枝）

题目

一个 \(1\) 到 \(n\) 的排列 \(x\) ，每次你可以选择任意一个满足 \(1\le i\le n\) 的 \(i\) ，将 \(x_1\)到\(x_i\) 翻转。你需要求出将排列变为升序的最小操作次数。有多组数据。

启发式搜索

下述的有序既可以是后一个比前一个大１，也可以是后一个比前一个小１

因为数字从１到n，不可能有重复数字出现，所以如果 \(x_i\) 与 \(x_{i-1}\) 满足有序， \(x_i\) 与 \(x_{i+1}\) 也满足有序，那么 \(x_{i-1}\) 到　\(x_{i+1}\) 均满足有序

而每次翻转，如果一段连续的区间完整的包含在操作区间里面，或是完全不在这之中，是不会影响其连续性的

可以推出，当满足有序的相邻点对数目为 \(n-1\) 时，这个序列要么是单调递增序列，要么是单调递减序列

那么搜索过程中就可以把满足有序的相邻点对数目这个作为判定是否找到答案的判定变量

设这个变量为 \(s\)

每次翻转会影响到与左右点的有序性的点只有 \(x_1\) 和 \(x_i\)

分别是

\(A.\ x_1\) 与 \(x_{i+1}\) 是否能够组成新的有序的使答案更接近我们要求的答案

\(B.\ x_i\) 与 \(x_{i+1}\) 原本是否已经组成了有序的而现在这个操作将其破坏掉了

根据这个我们会发现，对于枚举的一次操作　\(x_1-x_i\) 翻转，可能会有：

\(1.\ s=s-1,A==false\ \&\&\ B==true\)

\(2.\ s=s,A==true\ \&\&\ B==true\)

\(3.\ s=s+1,A==true\ \&\&\ B==false\)

对于结果１，我们是肯定不会选的　因为这只会让我们一直以来的努力全部木大

而结果２和结果３，都是有可能选的

到这里代码就比较显然了

接下去就需要考虑剪枝了

机房里刚学了一个月的巨佬跟我讲了一个特别优秀的剪枝

迭代加深之后，根据当前的 \(s\) 可以知道最优步数：即当前步数加上 \(s\) ，然后就可以根据这个期望步数剪枝（因为有迭代加深限制步数）

代码里还有我自己写的一堆奇奇怪怪的　剪枝　卡常小技巧

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAX=2e6+3;
int a[MAX];
int b[MAX];
// int c[MAX]={0,5,2,5,8,7,6,5};
int n;
int ans;
inline void jh(int &x,int &y){int z=x;x=y;y=z;}
inline void dfs(int x,int y,int z)
{
   if(x==0)
   {
       if(a[1]==n)
       {
           if(y!=z)ans=min(ans,y+1);
       }
       else ans=y;
       return;
       // if(ans==6)for(int i=1;i<=y;i++)printf("%d ",b[i]);printf("\n");
   }
   if(y==z||y>=ans)return;
   for(int i=2;i<=n;i++)
   {
       if(i==b[y])continue;
       int now=x;
       if(abs(a[1]-a[i+1])==1)now--;
       if(abs(a[i]-a[i+1])==1)now++;
       if(now>=x)continue;
       if(now+y+1>z)continue;
       b[y+1]=i;
       
       // bool bj=0;
       // for(int j=1;j<=y+1;j++)if(b[j]!=c[j])bj=true;
       // if(!bj)printf("i: %d , x:%d , y:%d\n",i,now,y+1);
       // if(!bj)for(int j=1;j<=n;j++)printf("%d ",a[j]);
       // if(!bj)printf("-->\n");
       for(int j=1;j<=(i>>1);j++)jh(a[j],a[i-j+1]);
       // if(!bj)for(int j=1;j<=n;j++)printf("%d ",a[j]);
       // if(!bj)printf("\n\n");
       dfs(now,y+1,z);
       if(ans!=0x3f3f3f3f)return;
       for(int j=1;j<=(i>>1);j++)jh(a[j],a[i-j+1]);
   }
   for(int i=2;i<=n;i++)
   {
       if(i==b[y])continue;
       int now=x;
       if(abs(a[1]-a[i+1])==1)now--;
       if(abs(a[i]-a[i+1])==1)now++;
       if(now!=x)continue;
       if(now+y+1>z)continue;
       b[y+1]=i;
       // bool bj=0;
       // for(int j=1;j<=y+1;j++)if(b[j]!=c[j])bj=true;
       // if(!bj)printf("i: %d , x:%d , y:%d\n",i,now,y+1);
       // if(!bj)for(int j=1;j<=n;j++)printf("%d ",a[j]);
       // if(!bj)printf("-->\n");
       for(int j=1;j<=(i>>1);j++)jh(a[j],a[i-j+1]);
       // if(!bj)for(int j=1;j<=n;j++)printf("%d ",a[j]);
       // if(!bj)printf("\n\n");
       dfs(now,y+1,z);
       if(ans!=0x3f3f3f3f)return;
       for(int j=1;j<=(i>>1);j++)jh(a[j],a[i-j+1]);
   }
}
LL rin()
{
   LL s=0;
   char c=getchar();
   bool bj=0;
   for(;(c>‘9‘||c<‘0‘)&&c!=‘-‘;c=getchar());
   if(c==‘-‘)c=getchar(),bj=true;
   for(;c>=‘0‘&&c<=‘9‘;c=getchar())s=(s<<1)+(s<<3)+(c^‘0‘);
   if(bj)return -s;
   return s;
}
int main()
{
   // freopen("3.out","w",stdout);
   int i,j;
   for(int t=rin();t>0;t--)
   {
       n=rin();
       int x=n-1;
       for(i=1;i<=n;i++)a[i]=rin();
       a[n+1]=0x3f3f3f3f;
       for(i=1;i<n;i++)if(abs(a[i]-a[i+1])==1)x--;
       ans=0x3f3f3f3f;
       for(i=1;true;i++)
       {
           dfs(x,0,i);
           if(ans!=0x3f3f3f3f)break;
       }
       printf("%d\n",ans);
   }
   return 0;
}

序列（搜索剪枝）

原文：https://www.cnblogs.com/zjjws/p/13449003.html