J2C. Turtle and Strings题解

题意

给定一个字符串 $s$, 要求将其拆分为若干个字符串 $t_1+t_2+...+t_k$ 的形式，要求相邻的两个字符串 $t_{i-1},t_i$ 互不相同，求能划分出来的字符串数量最大值。

解题方法

考虑贪心的去处理这个问题，也就是每次尝试划分当前能划分出来的最短字符串 $t_i$。

不难发现，当 $|t_{i-1}|>1$ 时，我们都可以划分出长度为 $1$ 的 $t_i$, 而当 $|t_{i-1}|=1$ 时，如果想划分出长度为 $1$ 的 $t_i$, 其充要条件是 $t_i\neq t_{i-1}$, 反之则一定会划分出长度为 $2$ 的 $t_i$。

接下来我们去证明为什么这样贪是对的。

如果说有比这样贪心做的更优解，那么一定是在某一个位置上没有取到暂时能取到的最小字符串。那么对于后面的待分解的字符串，就会减少一位可以提供贡献的值。而此时我们如果倒着去划分，所得到的最终贡献一定是小于等于之前的情况的（因为后面串的总长减小了，而相对关系却没变）。

例如对于 a|baabab，贪心的去做会划分出 a|b|aabab，而如果这个不是最优则说明 a|ba|abab 可以在 abab 中划分出比 aabab 更多的字符串。这显然是不可能的。

由此，贪心的正确性得证。

复杂度

时间复杂度:

$O(\sum{n})$

空间复杂度:

$O(\sum{n})$

Code

#include <bits/stdc++.h>
using namespace std;
int t,n;
string s;
signed main(){
	cin>>t;
    while(t--){
    	int nowlen=0,ans=0;
		//nowlen记录上一次划分的长度
    	cin>>n;
        cin>>s;
        for(int i=0;i<n;i++){
        	if(nowlen!=1){//上一次划分了长度非1的字符串
        		nowlen=1;//说明这一次一定可以划分长度为1的
        		ans++;
        	}else{//上一次划分的长度为1
        		if(s[i]!=s[i-1]){//如果当前字母与上一位不同，则说明可以继续划分长度为1的最优字符串
        			nowlen=1;
        			ans++;
        		}else{
        			nowlen=2;//否则只能让当前长度为2
        			if(i==n-1) ans--;//特判 因为如果是最后一位就构不成两个字母的字符串，只能和倒数第二位合体
        			i++;
        			ans++;
        		}
        	}
        }
        cout<<ans<<endl;
    }
	return 0;
}