Photoshoot

题目描述

农夫约翰为了赢得县集市上“最佳奶牛摄影师”的奖项，正试图拍出一张完美的照片。他有 $N$ 头奶牛（$2 \leq N \leq 2\cdot 10^5$，且 $N$ 为偶数）。 农夫约翰的奶牛有两种可能的品种：更恩西（Guernsey）和荷斯坦（Holstein）。 为了让照片尽可能美观，他希望将奶牛排成一列，使得尽可能多的更恩西奶牛处在队列中的偶数位置（队列的第一个位置是奇数位置，下一个是偶数位置，以此类推）。由于他与奶牛缺乏有效沟通，他实现目标的唯一方式是让奶牛对其队列的某些“前缀”进行自我翻转，而且这些前缀的长度必须为偶数（前缀指从第一头奶牛到第 $j$ 头奶牛的区间，其中 $j$ 为某个位置）。 请计算农夫约翰达到目标所需的最少翻转次数。

输入格式

第一行输入 $N$ 的值。 第二行输入一个长度为 $N$ 的字符串，表示奶牛从左到右的初始顺序。每个字符 'H' 表示一头荷斯坦奶牛，每个字符 'G' 表示一头更恩西奶牛。

输出格式

输出所需的最少翻转次数，占一行。

14
GGGHGHHGHHHGHG

1

提示

在此示例中，只需翻转由前六头奶牛组成的前缀即可。 GGGHGHHGHHHGHG (Before) -> HGHGGGHGHHHGHG (After) 翻转前，有四头更恩西位于偶数位置。翻转后，有六头更恩西位于偶数位置。不可能有超过六头更恩西位于偶数位置。 SCORING: 测试点 2-6 满足 $N\le 1000$。 测试点 7-11 无额外限制。 题目来源：Aryansh Shrivastava

标签: USACO|2022|Bronze

来源

USACO|2022|Bronze