BZOJ 2824: [AHOI2012]铁盘整理

标签（空格分隔）： OI-BZOJ OI-搜索

---

Time Limit: 10 Sec

Memory Limit: 128 MB

---

Description

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

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

Input

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

Output

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

Sample Input

5

2 4 3 5 1

Sample Output

5

---

Solution####

搜索，剪枝方法：可以发现每次翻转只会改变一对相邻的铁盘，那么翻转为有序至少需要翻转【不应该相邻的铁盘数】次。

---

Code####

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<bitset>

#include<vector>

using namespace std;

#define PA pair<int,int>

int read()

{

 	int s=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}

	return s*f;

}

//smile please

int n,a[51];

int ls[105],ans,sum,pr;

void dfs()

{

	if(sum+pr>=ans)return;

	if(pr==0&&a[1]==1)

	  {ans=sum;return;}

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

	   {

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

	   	for(int j=1;j<i+1-j;j++)

	   	    swap(a[j],a[i-j+1]);

	   	++sum;

		dfs();

	   	--sum;

	   	for(int j=1;j<i+1-j;j++)

	   	    swap(a[j],a[i-j+1]);

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

	   }

}

int main()

{

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

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

	n=read();

	for(int i=1;i<=n;i++)a[i]=read(),ls[a[i]]++;

	for(int i=1;i<=100;i++)ls[i]+=ls[i-1];

	for(int i=1;i<=n;i++)a[i]=(ls[a[i]]--);

	ans=n*2-2;

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

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

	       pr++;

	dfs();

	printf("%d\n",ans);

	//fclose(stdin);

	//fclose(stdout);

	return 0;

}