[CSP-X2025 山东] IOI 串

Luogu

IDLGB4426

Time1000ms

Memory512MB

DifficultyP3

2025山东枚举前缀和CSP-X 小学组线性 DP

小明对字符串 `IOI` 怀有特殊的感情，他定义一种由大写英文字母 `I` 和 `O` 构成的字符串为“好串”，当且仅当它可以被划分为三个非空部分，依次为：第一部分：连续非零个 `I` 第二部分：连续非零个 `O` 第三部分：连续非零个 `I` 如： `IIIOOIIII` 是一个好串，`IOI` 也是一个好串； `OIOI`，`IIO` 都不是好串。现在，小明有一个长度为 $n$ 的字符串 $S$，且 $S$ 仅包含字符 `I` 和 `O`。他可以进行任意次修改操作，每一次操作可将字符串中某一个位置的字符替换成另一个字符（即把 `I` 改为 `O`，或把 `O` 改为 `I`）。例如：当 $S = \tt{IIIOOOIOOII}$ 时，根据上述定义，$S$ 不是一个“好串”，但小明可以有多种方法通过修改操作把 $S$ 变为“好串”：方法 1：把第 7 个字符 `I` 改为 `O`，经过 1 次操作得到 `IIIOOOOOOII`；方法 2：分别把第 8 个和第 9 个字符 `O` 改为 `I`，经过 2 次操作得到 `IIIOOOIIIII`。可以确定，至少经过 1 次修改操作才能把上面的字符串 $S$ 变为“好串”。你的任务：告诉你小明的字符串 $S$，请你帮小明计算，至少需要进行多少次修改操作，才能将字符串 $S$ 变为一个“好串”。如果 $S$ 已经是一个“好串”，输出 $0$。 ## Input 一行，仅由 `I` 和 `O` 两种字符组成的字符串 $S$。 ## Output 一行，包含一个整数，表示把字符串 $S$ 修改为“好串”需要的最少的修改次数。 [samples] ## Note 【样例 3】见选手目录下的 `ioi/ex_ioi3.in` 与 `ioi/ex_ioi3.ans`。【样例 4】见选手目录下的 `ioi/ex_ioi4.in` 与 `ioi/ex_ioi4.ans`。【数据范围】对于所有的数据，字符串的长度 $n$ 满足 $3 \le n \le 5 \times 10^3$，且字符串中仅包含大写英文字母 `I` 和 `O`。 ::cute-table{tuack} | 测试点 | $n \le$ | 特殊性质 | |:------:|:-------------:|:--------------:| | $1$ | $1000$ | 字符全部为 `I` | | $2$ | $1000$ | 字符全部为 `O` | | $3\sim 13$ | $200$ | 无 | | $14\sim 20$ | $5 \times 10^3$ | 无 |

Samples

Input #1

IIIOOOIOOII

Output #1

Input #2

IOOIOOIOOOII

Output #2

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments