「BZOJ 2824」「AHOI2012」铁盘整理

Description

给定一个长度为 $n$ 互不相同的序列 $a_i$,每次操作可以将第 $1 \sim i\ (1 \leq i \leq n)$ 个数翻转,求最少几次操作可以使它变成升序数列。$(1 \leq n \leq 50, 1 \leq a_i \leq 100)$

Source

[BZOJ]2824

Solution

考虑 IDA*

先离散化,保证最后得到的数列为 $1,2,3, \ldots, n$ 。

本题中的 最完美估价

1
2
3
4
5
6
7
8
a[n + 1] = n + 1;

inline int h() {
int cnt = 0;
for (int i = 1; i <= n; ++i)
cnt += abs(a[i] - a[i + 1]) != 1;
return cnt;
}

显然一次翻转最多只能改变一对相邻数的差(比如翻转第 $1 \sim 3$ 个数只能改变第 $3$ 个数与第 $4$ 个数的差)。因此对于一个序列,有多少对相邻的数差不为 $1$,就至少要翻转多少次。不要忘记把第 $n + 1$ 个数设为 $n + 1$,因为如果翻转第 $1 \sim n$ 个数,我们也可以认为改变了第 $n$ 个数与第 $n + 1$ 个数的差。

Code

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 50;
int n, a[MAXN + 5], b[MAXN + 5];
bool sol;

inline int h() {//最完美估价
int cnt = 0;
for (int i = 1; i <= n; ++i)
cnt += abs(a[i] - a[i + 1]) != 1;
return cnt;
}

void dfs(int g, int f, int pre) {
if (sol || g + h() > f) return;//预估步数
if (!h()) {
sol = 1;//找到答案
return;
}
for (int i = 1; i <= n; ++i) {
if (i == pre) continue;//保证不与上一次翻转的长度相同
reverse(a + 1, a + i + 1);//翻转
dfs(g + 1, f, i);
reverse(a + 1, a + i + 1);//回溯
}
}

int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; ++i)
a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;//离散化
a[n + 1] = n + 1;
for (int i = 0; ; ++i) {//迭代加深
sol = 0;
dfs(0, i, 0);
if (sol) {
write(i);
putchar('\n');
break;
}
}
return 0;
}

本文标题:「BZOJ 2824」「AHOI2012」铁盘整理

文章作者:Heartlessly

发布时间:2019年05月15日 - 07:39:24

最后更新:2019年05月15日 - 16:41:30

原始链接:https://heartlessly.github.io/problems/bzoj-2824/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%