UVA-11212 Editing a Book （IDA*）

题目大意：将一个数字序列以最少的剪切次数粘贴成另一个数字序列。

题目分析：很显然，最坏的情况是需要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;

}