BZOJ2824 AHOI2012 铁盘整理

Description

在训练中，一些臂力训练器材是少不了的，小龙在练习的时候发现举重器械上的铁盘放置的非常混乱，并没有按照从轻到重的顺序摆放，这样非常不利于循序渐进的锻炼。他打算利用一个非常省力气的办法来整理这些铁盘，即每次都拿起最上面的若干个圆盘并利用器械的力量上下翻转，这样翻转若干次以后，铁盘将会按照从小到大的顺序排列好。那么你能不能帮小龙确定，最少翻转几次就可以使铁盘按从小到大排序呢？

例如：下面的铁盘经过如图2.1所示的以下几个步骤的翻转后变为从小到大排列。

Input

共两行，第一行为铁盘个数N（1≤N≤50）。

第二行为N个不同的正整数（中间用空格分开），分别为从上到下的铁盘的半径 R（1≤R≤100）

Output

一个正整数，表示使铁盘按从小到大有序需要的最少翻转次数。

Sample Input

5

2 4 3 5 1

Sample Output

IDA*，注意一下估价函数，在这里我们翻转一次只会改变两端的相邻的铁盘的大小关系，所以我们只用计算不可以放在一起的铁盘个数就好了

#include<bits/stdc++.h>

using namespace std;

#define N 60

struct Node{int val,id;}pre[N];

bool cmp(Node a,Node b){return a.val<b.val;}

int n,ans=1000,a[N];

int check(){

    int res=0;

    for(int i=2;i<=n;i++)

        if(abs(a[i]-a[i-1])!=1)res++;

    return res+(a[n]!=n);//********

}

bool judge(){

    for(int i=1;i<=n;i++)

        if(a[i]!=i)return 0;

    return 1;

}

bool dfs(int tmp,int up){

    if(tmp==up)return judge();

    if(check()+tmp>up)return 0;

    for(int i=2;i<=n;i++)if(a[i+1]-a[i]!=1){

        for(int j=1;j<=i/2;j++)swap(a[j],a[i-j+1]);

        if(dfs(tmp+1,up))return 1;

        for(int j=1;j<=i/2;j++)swap(a[j],a[i-j+1]);

    }

    return 0;

}

int main(){

//  freopen("2824.in","r",stdin);

//  freopen("2824.out","w",stdout);

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&pre[i].val),pre[i].id=i;

    sort(pre+1,pre+n+1,cmp);

    for(int i=1;i<=n;i++)pre[pre[i].id].val=i;

    for(int i=1;i<=n*2;i++){

        for(int j=1;j<=n;j++)a[j]=pre[j].val;

        if(dfs(0,i)){

            cout<<i;

            return 0;

        }

    }

    return 0;

}

铁盘