【递推】翻硬币

题目

1208. 翻硬币 - AcWing题库

---

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币，那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数

数据范围

输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1：

**********
o****o****

输出样例1：

5

输入样例2：

*o**o***o***
*o***o**o***

输出样例2：

1

解题

方法一：递推

思路

首先明确：

• 翻转相邻的两枚硬币对每枚硬币只有一种选择，对于第 x 枚硬币，和它一起翻转的是第 x+1 又或是 x-1 枚硬币没有区别，有区别的只是参照物的变化，翻转 x 和 x+1 以 x 为参照物时是翻转一枚硬币与其后面一枚，翻转 x-1 和 x 以 x-1 为参照物时同样也是是翻转一枚硬币与其后面一枚。为了方便起见，我们之后进行的每一次翻转都是翻转一枚硬币与其后面一枚。
• 如果通过每次翻转两枚相邻硬币，能从初识状态变为目标状态，则两个状态间必定相差偶数个不同状态的硬币，但是本题数据保证答案一定有解所以不用考虑无解的情况。
• 为使操作步数最小化，相同的两枚相邻硬币最多只能被翻转一次，因为翻转两次状态又变回去了，没有意义。

接下来代码中要做的就是：

正序遍历硬币，如果第 i 个位置在初始状态与目标状态中的面不同的话就翻转一次 i 和 i+1 这两枚硬币（代码中可以只翻转 i+1 ，因为遍历只会向后进行且只有一次，前面的状态（i）不用维护）并增加计数，遍历完成后得到的计数就是最小操作步数。

细节问题：

• 在完成遍历的操作后可以保证除了所有被遍历到的位置的硬币（也就是除了最后一枚硬币以外的虽有硬币）都与目标状态中相同，因为不同的时候在遍历过程中已经被翻转了，而题目又保证答案一定有解，所以最后一枚硬币也必然与结束状态中相同。
• 为什么这么做得到的一定是最小操作步数？
  设最小操作步数（最优解）是 $ans$ ，我们得到的步数是 cnt ：
  • 首先经过我们 $cnt$ 步操作之后得到的状态一定是与目标状态相同的，也就是说 $cnt$ 是一个合法解，那么一定有 $cnt \ge ans$ 。
  • 其次我们每一步都是在当前状态与目标状态不同时做出翻转的，每一步都是用于维护解的合法性，如果 $cnt > ans$ 那得到的 $ans$ 这个解一定不合法，与我们的命题相矛盾，所以一定有 $cnt \le ans$ 。
  • 综上 $cnt = ans$ 。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        char[] s = in.readLine().toCharArray();
        char[] t = in.readLine().toCharArray();
        int n = s.length, cnt = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (s[i] != t[i]) {
                s[i + 1] = s[i + 1] == '*' ? 'o' : '*';
                ++cnt;
            }
        }
        // 题目已经保证了有解 这步判断是多余的
        System.out.println(s[n - 1] == t[n - 1] ? cnt : -1);
    }
}