算法竞赛入门迭代加深搜索-编辑书稿

思路都在代码里，测试代码也都没删。

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;


int a[10],ai_j[10];
int n;
#define MAXD 9

bool isok(){
    for( int i=0; i<n-1; ++i) {
        if( a[i]>=a[i+1] ) return false;
    }
    printf("ok\n");
    return true;
}

//计算当前剩余未成功排列数
// 注意 h 是“后”关系，即前一个数和后一个数对不上 5 4 3 2 1 虽然3的位置没错，但结合4 3 ，3 2来看，h此时同样+1

int counth(){
  int cnt = 0;
    for( int i=0; i<n-1; ++i )
    {
        if(a[i]+1 != a[i+1]) ++cnt;
    }
    if( a[n-1]!=n ) ++cnt;
    return cnt;
}

// int count = 0;
bool dfs(int d, int maxd){
    // printf("第%d次调用\n", count++);
    // for(int k=0;k<n;k++)
    //     printf("%d ", a[k]);
    // printf("\n");
    //判断是否已经编辑成功
        //判断是否需要剪枝

    if(3*(maxd-d)<counth()){
        // printf("已剪枝\n");
        return false;
    }

    if(isok()) return true;
    int olda[10],b[10];
    // else printf("未剪枝\n");
    /*
        执行剪切操作
        从a[n]中取a[i]到a[j]，存入ai_j[n]后，将a[n]中剩余的数存入b[n]中
        将ai_j[n]中的数依次存入 b[0],b[1],b[2]...b[n]
    */
   memcpy(olda, a, sizeof(a));

   for(int i=0;i<n;i++)
    for(int j=i;j<n;j++){
        //从a[n]中取a[i]到a[j]，存入ai_j[n],将a[n]中剩余的数存入b[n]中
        int ii=0;
        for(int c=0;c<n;c++){
            if(c<i||c>j){
                b[ii] = a[c];
                ii++;
            }
        }
        //----------------------------------------
        // printf("ai_j: ");
        // for(int t=0;t<jj;t++)
        //     printf("%d ", ai_j[t]); cout<<endl;
        // printf("b: ");
        // for(int t=0;t<ii;t++)
        //     printf("%d ", b[t]); cout<<endl;
        //----------------------------------------

        //将ai_j[n]中的数依次存入 b[0],b[1],b[2]...b[n]
        for(int p=0;p<ii;p++){
            int ap=0;
            //将ai_j[n]插入位置p，p之前原封不动，p上插入ai_j，之后插入剩余b
            int beforep;
            for(beforep=0;beforep<p;beforep++) {a[ap] = b[beforep]; ap++;}
            for(int inp=i;inp<=j;inp++) {a[ap] = olda[inp]; ap++;}
            for(int behindp=p; behindp<ii; behindp++) {a[ap] = b[behindp]; ap++;}
            

            if(dfs(d+1,maxd)) return true;
            memcpy( a,olda,sizeof(a) );
        }

    }
    return false;
    
}


int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);

    int maxd=1;
    for(maxd=1; maxd<=MAXD; ++maxd){
        if(dfs(0,maxd)){
            printf("%d\n",maxd);
            break;
            }
    }

    getchar();
    getchar();
    return 0;
}