CodeForces 1025C Plasticine zebra

题目大意

题目链接 给定一个由w和b组成的字符串，可以操作任意次，每次操作（0次或多次）可以将字符串分割成左右两个子串，左、右侧子串均前后颠倒。 问最终字符串中最多可以有多少个w和b交错（w和b无所谓顺序）。

题解

构造，比较好想。 总述：

1. 当最左端字符与最右端字符不同时， max(左侧最长交错子串+右侧最长交错子串, 原最长交错子串)
2. 当最左端字符与最右端字符相同时，原最长交错子串

详解： 首先推断出试出最多操作一次，操作多了也没用。（这个我是通过试着造样例发现的这个特点） 当第一个字符和最后一个字符一样的时候，无论从哪里分割都没什么用，因为左右子串颠倒完，分割处的两个字符还是同为w或b，即无效操作。此时，我们就统计整个字符串中最长即可。 当第一个字符和最后一个字符不一样的时候 ，进行分割、颠倒属于有效操作。我们应当注意到，在操作完成之后，有可能更新最大长度的一定是包含分割处的一个交错子串。这个交错子串在分割处的左半部分是原字符串的最左端的若干字符，交错子串在分割处的右半部分是原字符串的最右端的若干字符串。因此我们要先求出，①原字符串中以第一个字符开始的交错子串长度，②原字符串中以最后一个字符结尾的交错子串长度。枚举分割处，分割处左侧能贡献的交错子串长度为min(分割处左侧子串的长度, ①)，分割处右侧能贡献的交错子串长度为min(分割处右侧子串的长度, ②)，二者之和与原字符串（即未进行操作）中的最长交错子串取个最大值即为答案。 注意：一个字符时最长交错子串长度为1（坑了我一发）

代码

#include
using namespace std;
string str;
int a[100010];
int main()
{
	cin>>str;
	int n = str.length();
	
	for(int i = 0;i