Java教程

洛谷 AT5158 题解

本文主要是介绍洛谷 AT5158 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目传送门

题目描述

  • 给定一个字符串 $ S $
  • 使得将这个字符串划分成 $ k $ 段后能够保证相邻的两段不相同。
  • 求出最大的 $ K $

我的思路

这道题可以用贪心来做

先遍历一遍，然后划分，定义一个字符串来记录选择的子串，如果当前选择的子串和上一个选择的子串不同，然后清空当前的字符串，计数器累加，最后输出计数器。

代码亲测有效

代码如下：

#include <bits/stdc++.h>
using namespace std;
string st,s1="",s2="";
int ans,i;
int main(){
	cin>>st;
	int len=st.length();
	while(i<len){
		s1=s1+st[i];
		if(s1!=s2){	//前后子串不一样 
		 	s2=s1,s1=""; 	//注意要清空	
			ans++;	//计数器累加 
		}
		i++;
	}
	cout<<ans<<endl;
	return 0;
}
这篇关于洛谷 AT5158 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航