1739: STEMA-C-5 河道清淤计划
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
某市水利局需要对一段河床进行清淤。
他们将该段河床划分为 2 × n 的网格矩阵，对于每个网格，评估其淤积程度，淤积程度分别用 H（严重淤积） 和 M （中等淤积）标记。
同时他们将网格矩阵划分为若干个清淤单元，每个清淤单元由三个位置相邻（上下左右）的网格组成。对于每个清淤单元，如果其中包含两个及以上严重淤积（用 H 标记）的网格，则该单元需要调用重型设备进行清淤，否则，只需要调用常规设备进行清淤，后者花费更小。
作为本次清淤工程的管理者，你需要设计一个划分清淤单元的方案，使得需要调用重型设备的清淤单元的数量最少，并输出这个最少数量。
例如：n = 6，2 × 6 的网格区域情况如下：
最优划分方案之一如下：
其中需要调用重型设备的清淤单元的数量为 1。
输入
第一行输入一个整数 n（3≤n<106，且 n 是 3 的倍数），表示网格矩阵的列数； 接下来两行，每行输入一个长度为 n 的字符串，其中仅包含大写字母 'H' 和 'M'，'H' 表示严重淤积网格，'M' 表示中等淤积网格。
输出
输出一个整数，表示需要调用重型设备的清淤单元的最少数量。
样例输入 复制
6
MHHHMH
MHHMMM样例输出 复制
1提示
动态规划
2025-6国考05