POJ 3460 Booksort(算竞进阶习题)

IDA*

这题真不会写。。估价函数太巧妙了。。

按照lyd神牛的说法我们把a[i+1]=a[i]+1记为正确后继，反之则记为错误后继

那么考虑最优的一次交换区间，至多能够纠正三个错误后继，所以我们统计序列的错误后继数n，n/3就是估价函数的值

因为把某区间移到后面和把另外一个区间移到它前面是等价的，所以我们按从左往右考虑区间后移即可

初始迭代深度为原序列最少需要的移动次数，移动次数+估价函数值超过迭代深度就直接返回搜索失败

每一次搜索完之后，最少移动次数（迭代深度）++

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int lowbit(int x){ return x & (-x); }

inline int read(){

    int X = 0, w = 0; char ch = 0;

    while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }

    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();

    return w ? -X : X;

}

inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }

inline int lcm(int a, int b){ return a / gcd(a, b) * b; }

template<typename T>

inline T max(T x, T y, T z){ return max(max(x, y), z); }

template<typename T>

inline T min(T x, T y, T z){ return min(min(x, y), z); }

template<typename A, typename B, typename C>

inline A fpow(A x, B p, C lyd){

    A ans = 1;

    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;

    return ans;

}

int _, n, maxdepth;

int f(int a[]){

    int tot = 0;

    for(int i = 1; i <= n - 1; i ++) if(a[i + 1] != a[i] + 1) tot ++;

    if(a[n] != n) tot ++;

    return tot;

}

// swap [x...k] and [k+1...y]

void move(int a[], int x, int k, int y){

    int tmp[20], i = 0, j = 0;

    for(i = k + 1, j = 0; i <= y; i ++, j ++)

        tmp[j] = a[i];

    for(i = x; i <= k; i ++, j ++)

        tmp[j] = a[i];

    for(i = x, j = 0; i <= y; i ++, j ++)

        a[i] = tmp[j];

}

bool dfs(int a[], int step){

    int h = f(a);

    //cout << h << endl;

    if(h == 0) return true;

    if(h + 3 * step > maxdepth * 3) return false;

    for(int i = 1; i < n; i ++){

        for(int k = i; k < n; k ++){

            for(int j = k + 1; j <= n; j ++){

                int tmp[20];for(int pos = 1; pos <= n; pos ++) tmp[pos] = a[pos];

                //for(int x = 1; x <= n; x ++) printf("%d ", tmp[x]); puts("");

                move(tmp, i, k, j);

                //for(int x = 1; x <= n; x ++) printf("%d ", tmp[x]); puts("");

                if(dfs(tmp, step + 1)) return true;

            }

        }

    }

    return false;

}

void IDAstar(int a[]){

    maxdepth = (int)ceil((double)f(a) / 3);

    if(maxdepth) while(maxdepth < 5 && !dfs(a, 0)) maxdepth ++;

    if(maxdepth == 5) printf("5 or more\n");

    else printf("%d\n", maxdepth);

}

int main(){

    scanf("%d", &_);

    for(; _ > 0; _ --){

        scanf("%d", &n);

        int b[20]; for(int i = 1; i <= n; i ++) scanf("%d", &b[i]);

        IDAstar(b);

    }

    return 0;

}