2024.3.29

2024.3.29 【人总是贪婪的，就像最开始，我也只是想知道你的名字。】

Friday 二月二十

P2534 AHOI2012 铁盘整理

//2024.3.29
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int
const int oo = 20;

itn gif(itn x){return x<0?-x:x;}

int n;
itn st[oo],sp[oo];
itn masp;
bool use;

int hope(){
    itn cnt = 0;
    for (itn i=1;i<=n;i++)
        if (gif(st[i]-st[i+1])!=1)
            cnt ++;
    return cnt;
}

void dfs(itn x,itn id,int step){
    if(step == masp){
        if (id == 0)
            use = 1;
        return ;
    }

    itn tmp;
    for (itn i=2;i<=n;i++){
        if (i==x||gif(st[i+1]-st[i])==1)
            continue;

        tmp = id;

        reverse(st+1,st+i+1);
        if (gif(st[i]-st[i+1])==1)
            tmp = id-1;

        if (tmp + step <= masp){
            dfs(i,tmp,step+1);
            if (use)
                return ;
        }

        reverse (st+1,st+i+1);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n;
    for (int i=1;i<=n;i++){
        cin >> st[i];
        sp[i] = st[i];
    }
    st[n+1] = n+1;

    sort (sp+1,sp+n+1);
    for (itn i=1;i<=n;i++)
        st[i] = lower_bound(sp+1,sp+n+1,st[i])-sp;

    for (;;masp++){
        dfs(1,hope(),0);
        if (use){
            cout << masp;
            return 0;
        }
    }

    return 0;
}

这是一个A*的典型题目，我们不妨来讨论一下A*

A*

我是oiwiki链接

A * 搜索算法（英文：A*search algorithm，A\ * 读作 A-star），简称 A * 算法，是一种在图形平面上，对于有多个节点的路径求出最低通过成本的算法。它属于图遍历（英文：Graph traversal）和最佳优先搜索算法（英文：Best-first search），亦是 BFS 的改进。

A*中最为关键，也是不同于普通bfs的一点，就在于它的期望函数（估价函数

估价函数的定义，首先要确定距离这一抽象概念，如本题中，将盘子大小顺序的差值定义为距离，所以本题中，我们还需要进行一次离散化。

顺便将离散化板子拍在这里：

for (int i=1;i<=n;i++){
    cin >> st[i];
    sp[i] = st[i];
}
st[n+1] = n+1;
sort (sp+1,sp+n+1);
for (itn i=1;i<=n;i++)
    st[i] = lower_bound(sp+1,sp+n+1,st[i])-sp;

通用的距离求解有三角形不等式等，同时A*可以搭配优先队列等实现神奇优化，求解k短路问题。