题解：P10841 【MX-J2-T2】Turtle and Strings

· · 题解

题目大意

给定字符串 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=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;
}