题解 P2534 【[AHOI2012]铁盘整理】
Shikita
2019-03-11 20:38:01
一道搜索题目
对于本题,我们需要将一个序列通过若干次区间翻转后,使得相邻两数差为1
考虑$A*$算法,我们需要找出最佳状态下翻转的次数,即至少为相邻两数差不为1的对数。考虑一个最优化剪枝,若当前步数加上最优化路径仍超过当前最优解,那么剪枝。我们可以再考虑,若我们当前满足条件,那么我们可以退出
Coding
```
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0;
char c=getchar();
bool flag=0;
while(c<'0'||c>'9'){if(c=='-')flag=1;c=getchar();}
while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();}
return flag?-x:x;
}
struct node{int x,id;}a[10005];
int cg[10005],ans,n,cnt;
inline bool cmp(node a,node b) {return a.x<b.x;}
inline int A()
{
int tot=0;
for(int i=1;i<=n;++i) if(abs(cg[i+1]-cg[i])!=1) ++tot;
return tot;
}
inline void dfs(int k,int cnt)
{
int l=A();
if (l==0&&cg[1]<cg[2]) {ans=k;return;}
if (ans||k+l>cnt||k==cnt) return;
for(int i=2;i<=n;++i)
{
if(abs(cg[i]-cg[i+1])==1) continue;
for(int j=1;j<=i/2;++j) swap(cg[j],cg[i-j+1]);
dfs(k+1,cnt);
for(int j=1;j<=i/2;++j) swap(cg[j],cg[i-j+1]);
}
}
int main()
{
n=read();for(int i=1;i<=n;++i) a[i].x=read(),a[i].id=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i) cg[a[i].id]=i;
cg[n+1]=n+1;
while(!ans) {dfs(0,cnt);++cnt;}
printf("%d",ans);
}
```