Mad Scientist

题目描述

农夫约翰的表弟本碰巧是个疯狂科学家。通常这会在家庭聚会中造成不少摩擦，但有时也会有所帮助——尤其是当农夫约翰在奶牛问题上遇到一些独特而不寻常的麻烦时。 农夫约翰目前正面临一个独特而不寻常的奶牛问题。他最近订购了 $N$ 头奶牛（$1 \leq N \leq 1000$），由两种不同品种组成：荷斯坦（Holstein）和更西（Guernsey）。他在订单中用一个长度为 $N$ 的字符串来指定奶牛的品种，每个字符要么是 H（表示 Holstein），要么是 G（表示 Guernsey）。不幸的是，当奶牛到达农场并被他排成一列时，它们的品种序列形成的字符串与原先的字符串不同。 我们将这两个字符串称为 $A$ 和 $B$，其中 $A$ 是农夫约翰最初希望得到的品种标识字符串，$B$ 是奶牛到达时他看到的字符串。农夫约翰并没有仅仅检查是否能通过重新排列 $B$ 中的奶牛得到 $A$，而是请表弟本用他的科学才智来帮助解决这个问题。 经过数月工作，本制造出了一台非凡的机器：multi-cow-breed-flipinator 3000。它能够对任意一个连续子串的奶牛切换品种：子串中所有的 H 变为 G，所有的 G 变为 H。农夫约翰想知道，最少需要使用这台机器多少次，才能把当前的排列 $B$ 变为他最初想要的排列 $A$。 遗憾的是，本的疯狂科学家技能仅限于制造巧妙装置，所以你需要帮助农夫约翰解决这个计算难题。

输入格式

第一行输入包含 $N$，接下来两行分别为字符串 $A$ 和 $B$。每个字符串都有 $N$ 个字符，且每个字符不是 H 就是 G。

输出格式

输出将 $B$ 转换为 $A$ 所需使用机器的最少次数。

7
GHHHGHH
HHGGGHH

2

提示

首先，FJ 可以只对对应第一个字符的子串进行变换，将 $B$ 变为 GHGGGHH。接着，他可以对由第 3 和第 4 个字符组成的子串进行变换，从而得到 $A$。当然，也存在其他同样只需使用两次机器的方案。 题目来源：Brian Dean

标签: USACO|2020|Bronze

来源

USACO|2020|Bronze