感谢群友XXX的真题投稿

题目内容

塔子哥是一名信息学竞赛的热爱者，他从小就对编程和算法有着浓厚的兴趣。他经常参加各种信息学竞赛，从NOIP到NOI，再到IOI，他都有着不俗的成绩。他的梦想是成为一名优秀的程序员，为人类社会贡献自己的智慧。

有一天，塔子哥收到了一个来自国际信息学奥林匹克竞赛（IOI）组委会的邀请函，邀请他参加一个特别的挑战。这个挑战是由一位神秘的信息学大师设计的，只有通过了这个挑战，才能得到大师的认可和指导。塔子哥对此感到非常兴奋，他立刻打开了邀请函中附带的链接，进入了一个在线评测系统。

思路:动态规划 + 前缀最值优化

Step1:朴素dp

考虑动态规划，做过Leetcode-132 或者 CodeFun2000-P1168 这种题的话，就会很自然的想到一个$O(n^2)$的朴素$dp$:

状态：

$dp_{i,j \in \{0,1\}}$ 代表考虑了字符串的前$i$个位置并且最后一段是$j$ 的最小修改次数。