自动搬运

查看原文

来自洛谷，原作者为

	block_in_mc 目标：参加 NOI 2026！

搬运于2025-08-24 23:01:46，当前版本为作者最后更新于2024-08-04 17:59:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定字符串 $s$，若字符串序列 $t$，满足 $s=t_1+t_2+\cdot\cdot\cdot+t_n$ 且 $t_i\not=t_{i+1}$，求 $t$ 长度的最大值。

解题思路

考虑贪心，尽量分为长度为 $1$ 的字符串，若不行再分为长度为 $2$ 的字符串。设目前正在考虑 $s_i$，上一个选择的字符串为 $l$：

• 若 $s_i\not=l$，则选择 $s_i$ 作为新的字符串；
• 否则，选择 $s_i$ 至 $s_{i+1}$ 作为新的字符串。

显然，若 $s_i=l$，选择 $s_i$ 至 $s_{i+1}$ 作为新的字符串总是合法，因为上一个选择的字符串长度为 $1$ 而 $s_i$ 至 $s_{i+1}$ 长度为 $2$，总不相等。

但是考虑字符串 aaaaabaa，切分为 a/aa/a/ab/a/?，这里剩下来的一个字符不能单独分，需要和前面的 a 合并。

再考虑字符串 aaaaaaaa，切分为 a/aa/a/aa/a/?，这里剩下来的 a 与前一个合并后为 aa，与前面重复，这里还可以将 aa 再与 aa 合并，变为 a/aa/a/aaaa。

但是这样是错误的。不难发现，a/aa/a/aaaa 可以再分为 a/aa/a/aaa/a，而类似的都可以这样做。综合考虑两种情况，发现最终答案就是考虑最后一个字符前的答案。

AC 代码

#include <bits/stdc++.h>
using namespace std;
int t, n;
string s;
int main() {
    cin >> t;
    while (t--) {
        cin >> n >> s;
        s = " " + s;
        string last;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (s.substr(i, 1) != last) last = s.substr(i, 1), cnt++;
            else if (i < n) last = s.substr(i, 2), cnt++, i++;
            else i++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}