UVA11212 Editing a Book
解析
详细可以查看lrj书。本题题解出自刘汝佳算法竞赛入门经典
本题可以用IDA*算法求解。不难发现n≤9时最多只需要8步,因此深度上限为8。IDA*的关键在于启发函数。考虑后继不正确的数字个数h,可以证明每次剪切时h最多减少3,因此当3d+h>3maxd时可以剪枝,其中d为当前深度,maxd为深度限制 (3) 。如何证明每次剪切时h最多减少3呢?如图7-19所示,因为最多只有3个数字的后继数字发生了改变(即图中的a, b, c),h自然最多减少3。
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 9;
int a[maxn];
int n, kase;
bool isSort(){
for(int i = 0; i < n - 1; ++i) if(a[i] >= a[i + 1]) return false;
return true;
}
int h(){
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 maxd){
if(d * 3 + h() > 3 * maxd) return false;
if(isSort()) return true;
int b[maxn], oldera[maxn];
memcpy(oldera, a, sizeof(a));
for(int i = 0; i < n; ++i){
for(int j = i; j < n; ++j){
int cnt = 0;
for(int k = 0; k < n; ++k) if(k < i || k > j){
b[cnt++] = a[k];
}
for(int k = 0; k <= cnt; ++k){
int cnt2 = 0;
for(int p = 0; p < k; ++p) a[cnt2++] = b[p];
for(int p = i; p <= j; ++p) a[cnt2++] = oldera[p];
for(int p = k; p < cnt; ++p) a[cnt2++] = b[p];
if(dfs(d + 1, maxd)) return true;
memcpy(a, oldera, sizeof(oldera));
}
}
}
return false;
}
int solve(){
int max_ans = 5;
for(int maxd = 0; maxd < max_ans; ++maxd){
if(dfs(0, maxd)) return maxd;
}
return max_ans;
}
int main(){
freopen("data.in", "r", stdin);
while(scanf("%d", &n) == 1 && n){
for(int i = 0; i < n; ++i)
scanf("%d", &a[i]);
printf("Case %d: %d\n", ++kase, solve());
}
return 0;
}