D. 古籍展架优化计划

256 MiB 1000 ms 标准输入输出
传统题 文本比较

题目描述

百年图书馆即将举办「丝绸之路古籍特展1,策展人需将空展架整理为特定古籍陈列序列。展架由n个格位组成,初始均为空槽(标记为)。每个格位需放置的文物用敦煌 文书编号表示(如 H =汉简, T =吐蕃卷轴,T = 回鹘文书,数字 1 =特殊藏品编码)。修复规则:文物修复团队每次操作可将任意连续区间的空槽或已有文物整体替换为另一个文物(如将 [3-5] 替换为 T ),另一个文物层会完全覆盖旧层。 注意:频繁替换会损伤文物,需计算最小替换次数以还原目标陈列序列,这对文物保护至关重要。

输入格式

一个长度不超过50的字符串,包含大写字母(H/T/U)或字符 1,作为目标陈列序列。

输出格式

输出一个整数,表示最少操作次数。

样例

输入: HTTUT

输出: 3

样例解释

1、覆盖全部为T,此时展架的状态为 TTTTT

2、覆盖第1位为H,此时展架的状态为 HTTTT。

2、覆盖第4位为U,此时展架的状态为HTTUT,达到目标陈列序列,最少的操作次数是3次。

说明:假如第一步全部覆盖为H,展架状态为HHHHH,第二步将2-3位覆盖为T,展架状态为HTTHH,第三步将第4位覆盖位U,展架状态为HTTUH。第四步将第5位覆盖为

T,展架状态为HTTUT,也可以达到目标陈列序列,但最终的步数是4,大于最少操作次数3次。采用其他覆盖方法,也无法找到比3次操作更少的可以达到目标陈列序列

的操作次数。