acwing-180. 排书

发表于 分类于 阅读次数： Waline： 本文字数： 599 阅读时长 ≈ 2 分钟

考点

  • DFS
  • IDAstar

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
int n, arr[maxn], backup[maxn][maxn];

int f() {
  int res = 0;
  for (int i = 0; i + 1 < n; ++i) {
    if (arr[i + 1] != arr[i] + 1) ++res;
  }
  // 向上取整
  return (res + 3 - 1) / 3;
}

bool check() {
  for (int i = 0; i < n; ++i) {
    if (arr[i] != i + 1) return false;
  }
  return true;
}

bool dfs(int depth, int mx) {
  // 最优性剪枝
  // 当前开销+未来最小开销都大于阈值，剪枝
  if (depth + f() > mx) return false;
  if (check()) return true;
  for (int l = 0; l < n; ++l) {
    for (int r = l; r < n; ++r) {
      // 等效性剪枝，只会朝后交换
      // 先前序列向后交换，和当前序列向前交换是等价的
      for (int k = r + 1; k < n; ++k) {
        memcpy(backup[depth], arr, sizeof(arr));
        int a, b;
        for (b = r + 1, a = l; b <= k; ++a, ++b) arr[a] = backup[depth][b];
        for (b = l; b <= r; ++a, ++b) arr[a] = backup[depth][b];
        if (dfs(depth + 1, mx)) return true;
        memcpy(arr, backup[depth], sizeof(arr));
      }
    }
  }
  return false;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> arr[i];
    int depth = 0;
    while (depth < 5 && !dfs(0, depth)) ++depth;
    if (depth >= 5)
      cout << "5 or more" << endl;
    else
      cout << depth << endl;
  }
  return 0;
}

思路

先考虑每一步的决策数量：

当抽取长度为i的一段时，有n - i + 1种抽法，对于每种抽法，有n - i种放法

（原本是n - i + 1种放法，去掉了放回原位那一种）。

另外，将某一段向前移动，等价于将交换的那段向后移动，因此每种移动方式被算了两遍；

所以每个状态总共的分支数量是： \[ \frac{\sum{\begin{array}{c} n\\ i=1\\ \end{array}\left( n-i \right) \cdot \left( n-i+1 \right)}}{2}=\frac{\left( 14\times 15 \right) +\left( 13\times 14 \right) \cdots +\left( 2\times 1 \right)}{2}=560 \] 题目说最多四步，最多\(560^4\)，有双向BFS和IDAstar两种，但是双向BFS试了N次放弃了，还贼难写...

估价函数设计：

  • 在最终状态下，每本书后面的书的编号应该比当前书多1

  • 每次移动最多会断开三个相连的位置，再重新加入三个相连的位置，因此最多会将3个错误的连接修正

    所以如果当前有tot个连接，那么最少需要tot/3向上取整次操作，估价函数就可以设计成这个： \[ f\left( s \right) =\lceil \frac{tot}{3} \rceil \]

如果当前层数加上f(s)大于迭代加深的层数上限，则直接从当前分支回溯。