Description
给定一个长度为 $n$ 互不相同的序列 $a_i$,每次操作可以将第 $1 \sim i\ (1 \leq i \leq n)$ 个数翻转,求最少几次操作可以使它变成升序数列。$(1 \leq n \leq 50, 1 \leq a_i \leq 100)$
Source
Solution
考虑 IDA* 。
先离散化,保证最后得到的数列为 $1,2,3, \ldots, n$ 。
本题中的 最完美估价:
1 | a[n + 1] = n + 1; |
显然一次翻转最多只能改变一对相邻数的差(比如翻转第 $1 \sim 3$ 个数只能改变第 $3$ 个数与第 $4$ 个数的差)。因此对于一个序列,有多少对相邻的数差不为 $1$,就至少要翻转多少次。不要忘记把第 $n + 1$ 个数设为 $n + 1$,因为如果翻转第 $1 \sim n$ 个数,我们也可以认为改变了第 $n$ 个数与第 $n + 1$ 个数的差。
Code
1 |
|