BZOJ2824: [AHOI2012]铁盘整理

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2824

Solution

第一次打IDA* (～￣▽￣)～
注意到实际所需步数一定是不小于“相邻点差值>1的对数”所以拿它做估价函数，做最优性剪枝，若当前步数加上估价大于当前答案则剪去。。。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll int
#define N 105
using namespace std;
inline ll read(){
    char ch=getchar(); ll f=1,x=0;
    while (ch>'9'||ch<'0'){if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
inline void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10); putchar(x%10+'0');
}
struct data{
    ll v,id;
}a[N];
ll pos[N],sum,n,ans;
bool cmp(data x,data y){return x.v<y.v;}
bool judge(){
    bool bo=true;
    for (ll i=1;i<=n;i++) bo=bo&&(pos[i]==i);
    return bo;
}
ll get(){
    ll t=0;
    for (ll i=2;i<=n;i++) t+=abs(pos[i]-pos[i-1])!=1;
    return t;
}
void dfs(ll x){
    if (judge()) {ans=min(ans,x);return;}
    if (x+get()>=ans) return;
    for (ll i=2;i<=n;i++){
            ll mid=i/2;
            for (ll j=1;j<=mid;j++) swap(pos[j],pos[i-j+1]);
            dfs(x+1);
            for (ll j=1;j<=mid;j++) swap(pos[j],pos[i-j+1]);
    }
}
int main(){
    n=read();
    for (ll i=1;i<=n;i++){
        a[i].id=i; a[i].v=read();
    }
    sort(a,a+1+n,cmp);
    for (ll i=1;i<=n;i++)
        pos[a[i].id]=i;
    ans=2*n-1;
    dfs(0);
    write(ans);
}