蓝桥杯翻硬币（思维、找规律、贪心）

蓝桥杯翻硬币问题解析

小明正在参与一个名为“翻硬币”的游戏。

桌面上摆放着一排硬币，这些硬币按照一定的顺序排列。为了表示硬币的正反面，我们采用符号 * 表示正面，而 o 表示反面（请注意这里的 o 是小写字母，并非数字零）。

例如，一种可能的排列方式为：oo*oooo

若此时同时翻转最左侧的两个硬币，则排列将变为：oooo***oooo

现在小明提出的问题是：在已知初始状态和期望达到的目标状态的前提下，每次操作只能翻转相邻的两个硬币，那么对于特定的局面，最少需要进行多少次这样的操作？

我们规定：将翻转相邻的两个硬币这一行为定义为一次操作，因此问题要求如下：

Input

两段长度相等的字符串，各自代表初始状态与期望达成的目标状态，且每段字符数量均未超过1000个。

Output

一个数值，用于表示实现目标所需的最少操作次数。

Sample Input

Sample Output

数据来源与研究基础

蓝桥杯

传送门：https://acmore.cc/problem/LOCAL/1599

分析：

首先将最终状态与初始状态进行整合，相同位置标