[IDA*]序列（sequence）

TEST 搜索

序列（sequence）

【题目描述】
给定一个1~n的排列x，每次你可以将x1~xi翻转。你需要求出将序列变为
升序的最小操作次数。有多组数据。
【输入数据】
第一行一个整数t表示数据组数。
每组数据第一行一个整数n，第二行n个整数x1~xn。
【输出数据】
每组数据输出一行一个整数表示答案。
【样例输入】

1
8
6 1 3 2 4 5 7

【样例输出】

7

【数据范围】
对于100%的测试数据，t=5，n<=25。
对于测试点1,2，n=5。
对于测试点3,4，n=6。
对于测试点5,6，n=7。
对于测试点7,8,9，n=8。
对于测试点10，n=9。
对于测试点11，n=10。
对于测试点i(12<=i<=21)，n=i。
对于测试点22,23，n=22。
对于测试点24,25，n=23。

Solution

考试的时候已经猜到是 IDA* 了，可是一直没想出来估价函数是啥，写了个迭代加深搜索骗了个暴力分。。。

考虑到这是一个排列，最终的状态一定是 num[i]+1==num[i+1]。
而每次交换最多只会改变一组相邻元素的差值
所以对于某一个状态，相邻的元素之差大于 $1$ 的个数就可以作为估价函数的值，因为最优解步数不小于这个。

#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 36;
int n;
int tmp[MAXN];
int num[MAXN];
int ans;
bool check(){
    for(int i=1;i<n;i++)
        if(num[i]+1!=num[i+1])
            return false;
    return true;
}
void SWAP(int l,int r){
    for(int i=l;i<=r;i++)
        tmp[i]=num[i];
    for(int i=r,j=l;i>=l;i--,j++)
        num[i]=tmp[j];
}
bool H(int x,int limit){
    int re=0;
    for(int i=1;i<n;i++){
        if(abs(num[i]-num[i+1])>1)
            re++;
    }
    return re+x<=limit;
}
void DFS(int x,int limit){
    if(x==limit+1){
        if(check())
            ans=limit;
        return;
    }
    for(int i=1;i<=n;i++){
        if(ans!=2*n+1)
            return;
        SWAP(1,i);
        if(H(x,limit))
            DFS(x+1,limit);
        SWAP(1,i);
    }
}
void solve(){
    ans=2*n+1;
    if(check()){
        puts("0");
        return;
    }
    for(int i=1;i<=2*n;i++){
        DFS(1,i);
        if(ans!=2*n+1)
            break;
    }
    printf("%d\n",ans);
}
int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    int kase;
    scanf("%d",&kase);
    while(kase--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        solve();
    }
    return 0;
}