{"problem":{"name":"[CSP-X2025 山东] IOI 串","description":{"content":"小明对字符串 `IOI` 怀有特殊的感情，他定义一种由大写英文字母 `I` 和 `O` 构成的字符串为“好串”，当且仅当它可以被划分为三个非空部分，依次为： 第一部分：连续非零个 `I` 第二部分：连续非零个 `O` 第三部分：连续非零个 `I` 如： `IIIOOIIII` 是一个好串，`IOI` 也是一个好串； `OIOI`，`IIO` 都不是好串。 现在，小明有一个长度为 $n","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4426"},"statements":[{"statement_type":"Markdown","content":"小明对字符串 `IOI` 怀有特殊的感情，他定义一种由大写英文字母 `I` 和 `O` 构成的字符串为“好串”，当且仅当它可以被划分为三个非空部分，依次为：\n\n第一部分：连续非零个 `I`\n\n第二部分：连续非零个 `O`\n\n第三部分：连续非零个 `I`\n\n如：\n\n`IIIOOIIII` 是一个好串，`IOI` 也是一个好串；\n\n`OIOI`，`IIO` 都不是好串。\n\n现在，小明有一个长度为 $n$ 的字符串 $S$，且 $S$ 仅包含字符 `I` 和 `O`。\n\n他可以进行任意次修改操作，每一次操作可将字符串中某一个位置的字符替换成另一个字符（即把 `I` 改为 `O`，或把 `O` 改为 `I`）。\n\n例如：\n\n当 $S = \\tt{IIIOOOIOOII}$ 时，根据上述定义，$S$ 不是一个“好串”，但小明可以有多种方法通过修改操作把 $S$ 变为“好串”：\n\n方法 1：把第 7 个字符 `I` 改为 `O`，经过 1 次操作得到 `IIIOOOOOOII`；\n\n方法 2：分别把第 8 个和第 9 个字符 `O` 改为 `I`，经过 2 次操作得到 `IIIOOOIIIII`。\n\n可以确定，至少经过 1 次修改操作才能把上面的字符串 $S$ 变为“好串”。\n\n你的任务：\n\n告诉你小明的字符串 $S$，请你帮小明计算，至少需要进行多少次修改操作，才能将字符串 $S$ 变为一个“好串”。如果 $S$ 已经是一个“好串”，输出 $0$。\n\n## Input\n\n一行，仅由 `I` 和 `O` 两种字符组成的字符串 $S$。\n\n## Output\n\n一行，包含一个整数，表示把字符串 $S$ 修改为“好串”需要的最少的修改次数。\n\n[samples]\n\n## Note\n\n【样例 3】\n\n见选手目录下的 `ioi/ex_ioi3.in` 与 `ioi/ex_ioi3.ans`。\n\n【样例 4】\n\n见选手目录下的 `ioi/ex_ioi4.in` 与 `ioi/ex_ioi4.ans`。\n\n【数据范围】\n\n对于所有的数据，字符串的长度 $n$ 满足 $3 \\le n \\le 5 \\times 10^3$，且字符串中仅包含大写英文字母 `I` 和 `O`。\n\n::cute-table{tuack}\n\n| 测试点 | $n \\le$       | 特殊性质       |\n|:------:|:-------------:|:--------------:|\n| $1$      | $1000$          | 字符全部为 `I` |\n| $2$      | $1000$          | 字符全部为 `O` |\n| $3\\sim 13$   | $200$           | 无             |\n| $14\\sim 20$  | $5 \\times 10^3$ | 无             |","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4426","tags":["2025","山东","枚举","前缀和","CSP-X 小学组","线性 DP"],"sample_group":[["IIIOOOIOOII","1"],["IOOIOOIOOOII","2"]],"created_at":"2026-03-03 11:09:25"}}