题意： 给出n（ 2<=n<=9) 个乱序的数组 要求拍成升序 每次 剪切一段加上粘贴一段算一次 拍成1 2 3 4 .。。n即可 求排序次数
典型的状态空间搜索问题 初始状态为输入 结束状态为升序
分析： 因为n最大为就 排列最多为9！=362880个 虽软这个数字不是很大 但是每次剪切都可能不是一个数组 所以枚举量还要大大增加 所以肯定要优化
这里用到了迭代加深搜索： 最大次数为9 所以将次数从0开始枚举 直到首先找到一个最小的答案
迭代加深搜索其实和暴力算法没什么两样 但是重要的是找到启发函数（剪枝） 这个剪枝很重要 大大缩短时间
这题可得启发函数： d为深度 h为不正确的数组 maxx为当前次数
可证明（见紫书）每一次操作 h最多减少三 本来是 d+h<=maxx 时可以成立
现在有方程 3d+h>3maxx 时剪枝
启发函数就是和迭代加深搜索一起用 起到大量剪枝的作用
#include<bits/stdc++.h> using namespace std; #define N 9 int n,a[N];bool judge(void) {for(int i=0;i<n-1;i++)if(a[i]>=a[i+1])return 0;return 1; }int h(void) {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; }bool dfs(int d,int maxx) {if(3*d+h()>3*maxx)return false;if(judge())return true;int olda[N],b[N];memcpy(olda,a,sizeof a);for(int i=0;i<n;i++)for(int j=i;j<n;j++){int cnt2=0;for(int k=0;k<n;k++)if(k<i||k>j)b[cnt2++]=a[k];for(int k=0;k<=cnt2;k++){int cnt=0;for(int p=0;p<k;p++)a[cnt++]=b[p];for(int p=i;p<=j;p++)a[cnt++]=olda[p];for(int p=k;p<cnt2;p++)a[cnt++]=b[p];if(dfs(d+1,maxx))return 1;memcpy(a,olda,sizeof a);}}return 0; }int solve(void) {if(judge())return 0;for(int maxx=1;maxx<=8;maxx++)if (dfs(0,maxx) ) return maxx; }int main() {int cas=0;while(scanf("%d",&n),n){for(int i=0;i<n;i++)scanf("%d",&a[i]);printf("Case %d: %d\n",++cas,solve());} }