AT5158 [AGC037A] Dividing a String

题目描述

• 给定一个字符串 $S$；

• 将该字符串划定为 $k$ 段，保证每一段不同

• 试求 $k$ 是多少

思路

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

只需从头扫到尾，记录现在选择的字符串，再用一个变量记录上一个选择的字符串，如果现在选择的字符串与上一个选择的不同，直接 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;
}