紫书搜索例题7-10 UVA

题目链接:

题意:

题解:

IDA*，每次改变深度上限去剪枝
代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 int n;
19 int a[15];
20 
21 bool is_sort(){
22     for(int i=1; i<=n; i++)
23         if(a[i] != i) return false;
24     return true;
25 }
26 
27 int h(){  // 估值函数，有几个位置不正确，就是 不连续的位置
28     int cnt = 0; 
29     for(int i=1; i<n; i++) 
30         if(a[i]+1 != a[i+1]) cnt++; 
31     if(a[n] != n) cnt++;
32     return cnt;
33 }
34 
35 
36 bool dfs(int cur,int maxd){
37     if((maxd-cur)*3 < h()) return false;  // 剪枝， 每剪切一次，最多使三个位置正确
38     if(is_sort()) return true;
39 
40     int b[15],olda[15];
41     memcpy(olda,a,sizeof(a));
42     for(int i=1; i<=n; i++)
43         for(int j=i; j<=n; j++){ // 枚举剪切位置
44             int cnt=1;
45             for(int k=1; k<=n; k++){
46                 if(k<i || k>j) b[cnt++] = a[k];  // 没有剪掉的数字
47             }
48 
49             for(int p=1; p<=cnt; p++){ // 枚举放在哪个位置
50                 int cnt2 = 1;
51                 for(int k=1; k<p; k++) a[cnt2++] = b[k];
52                 for(int k=i; k<=j; k++) a[cnt2++] = olda[k]; 
53                 for(int k=p; k<cnt; k++) a[cnt2++] = b[k];
54                 if(dfs(cur+1,maxd)) return true;
55                 memcpy(a,olda,sizeof(olda));
56             }
57         }
58 
59     return false;
60 }
61 
62 int solve(){
63     int maxd;
64     if(is_sort()) return 0;
65     for(maxd=1; maxd<=8; maxd++){ // 最多9个数字，最大也就移动8次
66         if(dfs(0,maxd)) return maxd;
67     }
68 }
69 
70 int main(){
71     int cas = 0;
72     while(scanf("%d",&n) && n){
73         for(int i=1; i<=n; i++)
74             a[i] = read();
75         printf("Case %d: %d
",++cas,solve());
76     }
77 
78     return 0;
79 }
紫书搜索 例题7-10 UVA

题目链接:

题意:

题解:

代码:

紫书搜索例题7-10 UVA
