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

好久没发题解了。为了保住社贡分，水一篇。 本题数据不算大，**IDA** + **dfs** 即可。注意剪枝等细节处理。 ## 题目大意 小龙在练习的时候发现举重器械上的铁盘放置的非常混乱，并没有按照从轻到重的顺序摆放，这样非常不利于循序渐进的锻炼。他打算利用一个非常省力气的办法来整理这些铁盘，即每次都拿起最上面的若干个圆盘并利用器械的力量上下翻转，这样翻转若干次以后，铁盘将会按照从小到大的顺序排列好。那么你能不能帮小龙确定，最少翻转几次就可以使铁盘按从小到大排序呢？ 简单来说，即求一个长度为 $n$ 且互不相同的数列 $\rm R$，每次将 $[1,i]$ 翻转，求最少翻转几次使得该序列单调递增。 ## 大体思路 首先看到数据范围，很容易想到搜索加优化加离散化。 用数组 $b$ 储存排序后的半径，用数组 $a$ 表示 $b$ 中第一次大于等于 $R_i$ 的元素的下标（离散化），用 $\text{lower\_bound}$ 实现即可。 离散化后，设计深搜的优化技巧。优化技巧无非几种：剪枝，迭代加深，预估（可行性剪枝）。对于本题，采用后两者。刚才的离散化有助于设计预估函数：对于一个序列，每次反转 $[1,i]$ 只能改变 $i,i+1$ 的差。因此有几对相邻数的差不为 $1$，就要翻转几次。 代码如下： ```cpp scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); b[i]=a[i]; }//输入 sort(b+1,b+n+1);//排序 for(int i=1;i<=n;i++){ a[i]=lower_bound(b+1,b+n+1,a[i])-b; }//离散化 a[n+1]=n+1;//翻转（n,n+1) ...... inline int step(){//预估函数 int ret=0; for(int i=1;i<=n;i++) ret+=(abs(a[i]-a[i+1])==1?0:1);//计算差不为 1 的个数。 return ret; } ``` 然后码一个暴力 $\rm{dfs+IDA}$，声明标记变量 $flag$。 - 判断预估函数的返回值：若为 $0$ 则表示满足，$flag$ 标为 $1$ 并返回； - 预估步数已经超过，则直接返回（剪枝）； - 扩展 $n$ 种区间，翻转递归并回溯。 ## 完整代码 ```cpp #include<bits/stdc++.h>//抄袭有奖 using namespace std; const int maxn=1e20; int n,a[maxn],b[maxn]; bool flag; inline int step(){ int ret=0; for(int i=1;i<=n;i++) ret+=(abs(a[i]-a[i+1])==1?0:1); return ret; }//预估函数 inline void dfs(int s,int f,int pre){ if(flag) return ; int num=step(); if(num==0) { flag=1; return ; }//成功 if(s+num>f) return ;//剪枝 for(int i=1;i<=n;i++){ if(i==pre) continue;//避免重复 reverse(a+1,a+i+1);//翻转 dfs(s+1,f,i);//递归 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]; } sort(b+1,b+n+1);//排序 for(int i=1;i<=n;i++){ a[i]=lower_bound(b+1,b+n+1,a[i])-b; } a[n+1]=n+1;//离散化 int i=0; while(1){ dfs(0,i,0); if(flag){ printf("%d",i); return 0; } i++; }//迭代加深 return 0; } ``` ## 后记 介绍部分函数的使用方法： - `lower_bound(start,end,a)` 返回单调不减数列 $[start,end)$ 中第一个不小于 $a$ 的元素地址。对于单调不增序列，可以添加迭代器 `lower_bound(start,end,a,greater<int>())`。 - `reverse(start,end)` 表示将 $[start,end)$ 翻转。