题目大意：将一个数字序列以最少的剪切次数粘贴成另一个数字序列。
题目分析：很显然，最坏的情况是需要n-1次剪切，搜索层数不多，但每一层的状态数目又非常庞大，适宜使用IDA*。考虑每一个序列后续不正确的数字个数h，每一次剪切最多3个数字后续数字发生改变，每次剪切最多可减少3个不正确的后续数字。所以在当前层d，最大层maxd时，最多可减少的不正确后续数字是3*(maxd-d)，若h>3*(maxd-d)，则剪枝，整理一下便是《入门经典》上的估价函数了。
代码如下：
# include<iostream>
# include<cstdio>
# include<map>
# include<string>
# include<cstring>
# include<algorithm>
using namespace std;
string goal;
int n;
bool dfs(int d,int maxd,string now)
{
if(d==maxd)
return now==goal;
int h=0;
for(int i=0;i<n-1;++i)
if(now[i+1]-now[i]!=1)
++h;
if(3*d+h>3*maxd)
return false;
for(int i=0;i<n;++i){
for(int j=i;j<n;++j){
for(int k=0;k<i;++k){
string p=now.substr(0,k);
string q=now.substr(i,j-i+1);
string r=now.substr(k,i-k);
string t=now.substr(j+1,n-j);
if(dfs(d+1,maxd,p+q+r+t))
return true;
}
}
}
return false;
}
int main()
{
int a,cas=0;
while(scanf("%d",&n)&&n)
{
string start="";
for(int i=0;i<n;++i){
scanf("%d",&a);
start+=char(a+‘0‘);
}
goal="";
for(char c=‘1‘;c<=‘0‘+n;++c)
goal+=c;
for(int maxd=0;;++maxd){
if(dfs(0,maxd,start)){
printf("Case %d: %d\n",++cas,maxd);
break;
}
}
}
return 0;
}
UVA-11212 Editing a Book （IDA*）
原文：http://www.cnblogs.com/20143605--pcx/p/4843477.html