本题的关键是应用IDA*算法，降低时间复杂度，启发函数的发现和推导是重点。

对于可以用回溯法求解但解答树的深度没有明显上限的题目，可以考虑使用迭代加深搜索。设计一个乐观估计函数，预测从当前节点至少还学要扩展几层才有可能得到解，则状态空间搜索变成了IDA*算法。

刚开始吧状态定义为typedef  int  State[12]，但后来发现编译器老是报错并且极易出现各种错误，索性直接定义为一个struct。

#include 
    
     using namespace std;struct State{    int a[12];};int n, kase = 0, maxd;int getH(State cur){    int cnt = 0;    for(int i = 0; i < n-1; ++i)        if(cur.a[i]+1 != cur.a[i+1])            cnt++;    return cnt;}bool DFS(int d, State u){    int H = getH(u);    if(d == maxd) return H == 0;    if(3*d + H > 3*maxd) return false;    for(int x = 0; x < n - 1; ++x)        for(int l = 1; l <= x+1; ++l)            for(int r = 1; r <= n-x-1; ++r){                State v; memcpy(v.a, u.a, sizeof(u.a));                for(int i = x - l + 1, j = x + r - l + 1; i <= x; ++i, ++j)                    v.a[j] = u.a[i];                for(int i = x + 1, j = x - l + 1; i <= x + r; ++i, ++j)                    v.a[j] = u.a[i];                if(DFS(d + 1, v)) return true;            }    return false;}int main(){    ios::sync_with_stdio(false);    while(cin >> n && n){        State beg;        for(int i = 0; i < n; ++i)            cin >> beg.a[i];        for(maxd = 0; ; ++maxd)            if(DFS(0, beg))                break;        printf("Case %d: %d\n", ++kase, maxd);    }    return 0;}