侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【递推】翻硬币

GabrielxD
2023-02-17 / 0 评论 / 0 点赞 / 179 阅读 / 1,120 字
温馨提示:
本文最后更新于 2023-02-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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

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

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

细节问题:

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

评论区