poj 3460 Booksort

機智美麗勤勞而善良的你幫可憐的管理者整理整理書架吧

題目大意：

有N（1 ≤ N ≤ 15）本書，每本與每本的高度都不一樣。現在可以按照以下的辦法整理書：抽出一摞書，再保持原來的順序插進一個位置。這樣的話我們稱之為“一次操作”。現在你需要求出至少需要經過幾次操作才能讓書變成按高度升序的狀态。如果需要5次或者多于5次，隻需要輸出“5 or more”。

分析：

很明顯，要用id_dfs+a_star

經典的剪枝：

如果後繼值錯誤數目除以3加上目前已走步數已超過了最大步數，剪掉?_?為什麼呢

因為我們沒進行一次操作最多改變3個數字的後繼值

代碼如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=+;
int cas,n,shelf[maxn],maxdep,flag;
bool a_star(int dep){
    int cnt=;
    for(int i=;i<n;i++)
        if(shelf[i+]!=shelf[i]+)
            cnt++;
    if(cnt+dep*>maxdep*)//不能寫=啊！！！WA了一萬遍
        return false;//一定要*3要不然會很麻煩的    
    return true;
}
bool check(){
    for(int i=;i<n;i++)
        if(shelf[i]>shelf[i+])
            return false;
    return true;
}
void change(int a,int b,int c,int d){
    int len1=b-a+,len2=d-c+,ss[maxn];
    for(int i=a;i<=b;i++)
        ss[i+len2]=shelf[i];
    for(int i=c;i<=d;i++)
        shelf[i-len1]=shelf[i];
    for(int i=a;i<=b;i++)
        shelf[i+len2]=ss[i+len2];
}
bool id_dfs(int dep){
    if(dep>maxdep)
        return false;
    if(!a_star(dep-))
        return false;
    for(int k=;k<n;k++){
        for(int i=k;i>=;i--){
            for(int j=k+;j<=n;j++){//swap((i,k),(k+1,j))
                change(i,k,k+,j);
                if(check())
                    return true;
                if(id_dfs(dep+))
                    return true;
                change(i,i+(j-(k+)),i+(j-(k+))+,j);
                }
        }
    } 
    return false;
}
int main(){
    scanf("%d",&cas);
    while(cas--){
        scanf("%d",&n),flag=;
        for(int i=;i<=n;i++)
            scanf("%d",&shelf[i]);
        if(check()){
            printf("0\n");
            continue;
        }//一定要特判 ！！！！
        for(int i=;i<=;i++){
            maxdep=i;
            if(id_dfs()){
                printf("%d\n",maxdep),flag=;
                break;
            }
        }
        if(!flag)
            printf("5 or more\n");
    }
    return ;
} 
           

by >o< neighthorn