题解 P2534 【[AHOI2012]铁盘整理】

Shikita

2019-03-11 20:38:01

Solution

一道搜索题目 对于本题,我们需要将一个序列通过若干次区间翻转后,使得相邻两数差为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); } ```