https://vjudge.net/problem/UVA-11212
题意：给出n个自然段组成的文章，将他们排列成1,2...，n。每次只能剪切一段连续的自然段，粘贴时按照顺序粘贴。
思路：状态空间的搜索问题。
首先介绍一下IDA*，它属于DFS，在DFS遍历的时候，设定一个深度上限maxd，当前结点n的深度为g（n），乐观估价函数为h（n），则当g（n）+h（n）>maxd时应 该剪枝。这样的算法就是IDA*。
在这道题目中，由于最多就9个数，所以最多只需要剪切8次肯定是可以完成升序排列的。所以最大深度可以从1开始一直到8，依次去寻找是否能成功。
在这题中最重要的剪枝就是考虑后继不正确的数字个数h，可以证明每次剪切时h最多减少3，因此如果3*（maxd-d）<h，则可以直接剪枝。因为此时即使一直遍历到限定深 度maxd，也无法将h的个数减为0。另外也还有许多地方可以剪枝，下面的代码中我有仔细介绍。
#include<iostream>
#include<string>
#include<cstring>
using namespace std; int n;
int a[]; bool goal() //判断是否已达到最终状态
{
for (int i = ; i < n - ; i++)
{
if (a[i]>a[i + ]) return false;
}
return true;
} int h() //计算后继不正确的个数
{
int number = ;
for (int i = ; i < n-; i++)
{
if (a[i + ] != a[i] + )
number++;
}
if (a[n - ] != n) number++;
return number;
} bool dfs(int d, int maxd)
{
if ( * d + h()> * maxd) return false; //剪枝
if (goal()) return true;
int pre[]; //保存原来序列
int cut[]; //保存剪切后的序列
for (int i = ; i < n; i++) //枚举，i为剪切起点，j为剪切终点
{
if (i == || a[i] != a[i - ]+) //剪枝，不破坏连续的数字片段
{
for (int j = i; j < n; j++)
{
while (a[j + ] == a[j] + ) j++; //剪枝，如果一个数字片段已经连续，则不要去破坏它
memcpy(pre, a, sizeof(a));
int cnt = ;
for (int k = ; k < n; k++) //保存剪切后的序号
{
if (k<i || k>j)
cut[cnt++] = a[k];
}
for (int k = ; k <= cnt; k++) //枚举，依次插入到第k个位置之前
{
int cnt2 = ;
for (int t = ; t < k; t++) a[cnt2++] = cut[t];
for (int t = i; t <= j; t++) a[cnt2++] = pre[t];
for (int t = k; t < cnt; t++) a[cnt2++] = cut[t];
if (dfs(d + , maxd)) return true; //继续深搜
memcpy(a, pre, sizeof(pre)); //如果失败，则恢复a[]的原来的数字片段
}
}
}
}
return false;
} int solve()
{
if (goal()) return ;
for (int i = ; i < ; i++) //最多只需要进行8次dfs即可获得最终状态
{
if (dfs(, i)) return i;
}
} int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int kase = ;
while (cin >> n && n)
{
memset(a, , sizeof(a));
for (int i = ; i < n; i++)
cin >> a[i];
int ans=solve();
cout << "Case " << ++kase << ": " << ans << endl;
}
}