P14719 [RMI 2025] Cheap AI
题目描述
给定一个数 $K$ 和一个由英文小写字母组成的字符串 $S$，选择一个非空串 $t$，满足 $1 \le |t| \le K$，将 $t$ 在 $S$ 中出现的位置（选择若干个且互不重叠）替换为特殊字符 `#`，使得得到的最终字符串的长度最小。
求出这个最小长度。
### 实现细节
你需要实现下列函数：
```cpp
int solve(int K, std::string S);
```
这个函数接收 $K$ 和 $S$ 作为参数，需要求出在把一个长度不超过 $K$ 的所选 token 的若干次出现（互不重叠）替换为特殊字符 `#` 之后得到的字符串的最小长度。
输入格式
见「实现细节」。
输出格式
见「实现细节」。
说明/提示
#### 样例解释
- 样例一解释：我们选择 $t = \texttt{aabaa}$，于是 $S$ 变为 $\texttt{\#bacbb\#}$（长度为 7）。
- 样例二解释：我们选择 $t = \texttt{aaaaaa}$，于是 $S$ 变为 $\texttt{\#\#\#a}$（长度为 4）。
#### 约束
* $1 \le K \le |S| \le 200\,000$
* $S$ 由英文小写字母组成。
| # | 分值 | 限制 |
|:-:|:-:|---|
| $1$ | $5 $| $S_i = \texttt{a}$ |
| $2$ | $7 $| $\vert S\vert \le 100$ |
| $3$ | $12$ | $\vert S\vert \le 5000$ |
| $4$ | $40$ | $\vert S\vert \le 75\,000$ |
| $5$ | $36$ | $\vert S\vert \le 200\,000$ |