zcmimi's blog
avatar
zc
2020-09-23 21:26:00
  • 本文总阅读量

查看原题

点击跳转

使用ida*

首先将数组离散化为1,2,\dots,n

一次翻转最多只能改变一对相邻数的差,

因此对于一个序列,有多少对相邻的数差不为1,就至少要翻转多少次。

估价函数:

a[n+1]=n+1;
int h(){
    int cnt=0;
    for(int i=1;i<=n;++i)cnt+=(a[i]!=a[i+1]+1&&a[i]!=a[i+1]-1);
    return cnt;
}
#include<bits/stdc++.h>
const int N=100011;
int n,mxd,a[N],b[N];
bool sol;
int h(){ // 估价函数
    int cnt=0;
    for(int i=1;i<=n;++i)cnt+=(a[i]!=a[i+1]+1&&a[i]!=a[i+1]-1);
    return cnt;
}
void dfs(int g,int pre){
    if(sol||g+h()>mxd)return;
    if(!h())return sol=1,void();
    for(int i=1;i<=n;++i)if(i!=pre){
        std::reverse(a+1,a+i+1);
        dfs(g+1,i);
        std::reverse(a+1,a+i+1);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i),b[i]=a[i];
    std::sort(b+1,b+n+1);
    for(int i=1;i<=n;++i)a[i]=std::lower_bound(b+1,b+n+1,a[i])-b;
    a[n+1]=n+1;
    for(int i=0;!sol;++i){
        mxd=i,dfs(0,0);
        if(sol)printf("%d\n",i);
    }
}
LG 2534 [AHOI2012]铁盘整理
comment评论
Search
search