IDA* 算法
在迭代加深的基础上增加 f() 的估值函数。
如果当前消耗的修改次数+估值修改次数,超过了限制的 maxDepth 的话,直接返回 false
import java.util.*;
class Main {
static int n;
static int N = 20;
static int[] w = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
n = sc.nextInt();
for (int i = 1; i <= n; i++) w[i] = sc.nextInt();
int depth = 0;
while (depth <= 5 && !dfs(0, depth)) depth++;
if (depth >= 5) System.out.println("5 or more");
else System.out.println(depth);
}
}
// 通常爆搜函数的设计:要么是已经消耗了多少次交换次数,或者当前是第几次交换,这两种定义
// 当前消耗的修改次数为 u;最多修改次数为 maxDepth
static boolean dfs(int u, int maxDepth) {
if (u + f() > maxDepth) return false;
if (f() == 0) return true;
for (int len = 1; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int k = r + 1; k <= n; k++) {
int[] clone = w.clone();
int[] nw = move(w, l, r, k);
w = nw;
if (dfs(u + 1, maxDepth)) return true;
w = clone;
}
}
}
return false;
}
static int[] move(int[] arr, int l, int r, int k) {
int[] ans = new int[N];
int idx = 1;
for (int i = 1; i <= l - 1; i++) ans[idx++] = arr[i];
for (int i = r + 1; i <= k; i++) ans[idx++] = arr[i];
for (int i = l; i <= r; i++) ans[idx++] = arr[i];
for (int i = k + 1; i <= n; i++) ans[idx++] = arr[i];
return ans;
}
static int f() {
int ans = 0;
for (int i = 1; i < n; i++) {
if (w[i] != w[i + 1] - 1) ans++;
}
// 这里其实是想计算 ans / 3 的上取整
// a / b 的上取整 = (a + b - 1) / b 的下取整
return (ans + 2) / 3;
}
}