【题解】UVa 11212【Editing a Book】

分析

这里可以用A*求解,不难发现原题数据最多只需$8$步。因此深度上限$8$,后面发现更优的上限为$5$,启发函数考虑不正确的数字个数$cnt$,不难发现当$3 \times d + cnt > 3 \times maxd$时可以剪枝。

代码

#include<cstdio>
#include<cstring>

const int MAXN = 9 + 6;
int n,A[MAXN];

bool isSorted(){
    for(int i = 0;i < n - 1;i++) if(A[i] >= A[i + 1]) return false;
    return true;
}

int oysj(){
    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 AStar(int d,int MAXD){
    if(d * 3 + oysj() > MAXD * 3) return false;
    if(isSorted()) return true;

    int B[MAXN],olda[MAXN];
    memcpy(olda,A,sizeof(A));
    for(int i = 0;i < n;i++) for(int j = 0;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++] = olda[p];
            for(int p = k;p < cnt;p++) A[cnt2++] = B[p];
            if(AStar(d + 1,MAXD)) return true;
            memcpy(A,olda,sizeof(A));
        }
    }
    return false;
}

int solve(){
    if(isSorted()) return 0;
    int maxAns = 5;
    for(int MAXD = 1;MAXD < maxAns;MAXD++) if(AStar(0,MAXD)) return MAXD;
    return maxAns;
}

int main(){
    int id = 0;
    while(scanf("%d",&n) == 1 && n){
        for(int i = 0;i < n;i++) scanf("%d",&A[i]);
        printf("Case %d: %d\n",++id,solve());
    }

    return 0;
}