解题报告 P2534 [AHOI2012]铁盘整理

题目内容

P2534

若干个铁盘，乱摆的，每次操作可以反转最上面的若干铁盘，求最少操作次数使得从上往下铁盘半径依次递增

解题思路

纪念人生中第一道紫题虽然这道题我不觉得他配紫

这种题可以使用IDA*进行玄学的搜索，好的进入正题。

众所周知，IDA*是需要一个估价函数的，而这道题的关键就在于估价函数如何来设计。一开始想过不在预定位置上的铁盘个数作为估价函数，发现不行，因为有可能你4个铁盘都不在指定位置上，但是反转一下就得到结果了，这样的估价函数显然是不行的。

所以这里的估价函数只好使用不应该相邻的铁盘的个数，因为只有这样才能得到最接近的结果。至于如何判断不应该相邻的铁盘，我使用了 map 因为疯狂使用 stl 导致我跑的龟慢，然后就是常规的 IDA*，每次枚举一个深度 idt，然后让 dfs 在这个限定的深度里面跑，如果跑得出结果那就输出，跑不出那就加大 idt 继续跑。

细节上使用的是用 vector 模拟状态，（虽然好用但是跑的龟慢），每次操作使用 reverse 函数模拟，然后进行操作模拟的时候就不要只翻转第一层了，翻了等于没翻。

注意 stl 函数的尿性都是左闭右开区间，差点被坑了

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int n;
vector<int> r0,r1;//r0是从上到下的初始顺序，r1是整理过的从上到下递增的顺序
map<int,int> m1,m2;//m1存储他上面应该是什么，m2存储他下面应该是什么

int h(vector<int> rcur)//估价函数
{
    int cnt=0;
    for(int i=0;i<r1.size()-1;i++)
    {
        if(m1[rcur[i]]!=rcur[i+1]&&m2[rcur[i]]!=rcur[i+1])
            cnt++;
    }
    return cnt;
}

bool iddfs(vector<int> rcur,int d,int idt)//迭代加深搜索
{
    if(d+h(rcur)>idt)//如果估价函数显示直接挂就返回
        return 0;
    if(d>idt)//如果深度挂了，返回
        return 0;
    if(rcur==r1)//如果到达目标了，返回
        return 1;
    for(int i=2;i<=rcur.size();i++)//开始枚举翻的盘片
    {
        vector<int> tmp=rcur;
        reverse(tmp.begin(),tmp.begin()+i);//注意左闭右开
        if(iddfs(tmp,d+1,idt))//继续下一层搜索
            return 1;
    }
    return 0;
}

int main()
{
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        r0.push_back(x);
    }
    r1=r0;
    sort(r1.begin(),r1.end());//将排好序的铁盘做预处理
    for(int i=0;i<r1.size();i++)//对m1,m2进行预处理
    {
        if(i!=0)
            m1[r1[i]]=r1[i-1];
        if(i!=r1.size()-1)
            m2[r1[i]]=r1[i+1];
    }
    for(int idt=1;idt<=2<<n;idt++)//idt 的上限随便搞一个很大的数就行了
    {
        if(iddfs(r0,0,idt))
        {
            printf("%d\n",idt);
            return 0;
        }
    }
    return 0;
}