题目描述

  • 给定一个字符串 SS

  • 将该字符串划定为 kk 段,保证每一段不同

  • 试求 kk 是多少

思路

本题适合我这样的萌新练习贪心大法

只需从头扫到尾,记录现在选择的字符串,再用一个变量记录上一个选择的字符串,如果现在选择的字符串与上一个选择的不同,直接 Ans++, 并将上一个选择的字符串改为现在选择的字符串,清空现在的字符串。

证明显然

参考程序

#include <bits/stdc++.h>
using namespace std;

string S;

int Ans;

string Last , Now;

int main() {
	ios::sync_with_stdio(false);
	
	cin >> S;
	
	for(int i = 0; i < S.size(); i++) {
		Now += S[i];
		if(Last != Now) {
			Last = Now;
			++Ans;
			Now = "";
		}
	}
	
	cout << Ans << endl;
	
	return 0;
}