这一题是来自YBTOJ的题目，题目中运用到了贪心，缩点和分类讨论的思想。

题目描述

输入输出格式

样例输入输出

数据范围

思路

  考虑到可能有人看不懂它是怎么个“竖着摆“法，这里贴个图,对于样例一：

  就是这么个竖着摆法。
  然后就可以发现，当这一列有一个地方可以进行消除操作的时候，这一整条都必然会被消除，唯一不能进行操作的时候是1010这种没有两个色块连在一起的货色。
  可以举个例子，假设我们现在有一块全是1的连续色块，假设它的长度为2。那么它的上面和下面（假设有上面和下面）必然是0这个色块，或者不是色块。因为如果是上面和下面的色块是1的话，那这个色块肯定会包含在我们假设出来的这个色块里。而我们进行删除操作是会保留一个反转数字的，比如0变成1,1变成0，这样就必然会又产生一个色块。
  上一段的思想是解题的关键，想通之后我们就会发现，其实完全没必要对着这么长一段1010进行处理，我们可以把1110看成2 1，用2来代表这是一个可以进行删除操作的色块，1代表不能进行处理的，同理01101可以化简成为1211，这样可以更方便的进行处理。
  然后经过模拟样例（如果你还不知道样例的输出是怎么来的，请按照上面两段的思想去模拟一遍，这大有裨益）我们会发现，2处于不同位置的时候，会有不同的答案，比如121和211和112，这三种情况，虽然缩点化简后都只有两个1和一个2，但是进行的操作不尽相同，譬如对于121，首先对2进行操作，然后整个序列变成2，最后变成1，一共需要两步，211和112则需要三步。
  故而能发现，当2消除的时候，会带动旁边两个1一起消除（如果它不处于边界的话）所以当化简后的序列中心有一个2的时候，最优解为N(序列长度)/2+1。当序列只有左端有2的时候，我们当然希望它尽可能地靠右，用下面这个图来举例。

  选第二位的2进行删除操作，只进行一次，它就到达了边界，效率开始变低，选第三位的2进行操作的时候，却需要两次操作才能抵达边界，效率会更高，此时最优解为N-X（选中的2的位置）+1
  同样的道理，在右端的2希望我们希望它更靠近左边，此时最优解为X
  当左端和右端都存在2的时候，可以在两种情况中选择，一种是操作左边的2在不影响右边的2的情况下，以最小代价，消除掉一些区间，之后右边的2的右边的序列长度会等于左边的2的左边的序列长度，这种情况下最优解为N/2+1,或者可以选择同时操作两边，把中间的一段消除，这样左右两边肯定也能消除，答案为R(右边2的位置)-L(左边2的位置)+1

代码

#include
using namespace std;
int x[100086];
string s;
int main()
{
	int n,m;
	int ans=0;
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		cin>>s;
		int num=0;
		
		for (int j=0;j<s.size();j++)
		{
			int k=j;
			while(k<s.size()-1&&s[k+1]==s[j])
			{
				k++;
			}
			if(j<k)x[++num]=2;
			else x[++num]=1;
			j=k;
		}
		
		if((num&1)&&x[num/2+1]==2){ans+=num/2+1;continue;}
		int mid=num/2;
		int left=-1;
		for (int j=mid;j>=1;j--)
		{
			if(x[j]==2)
			{
				left=j;break;
			}
		}//搜左边的可消除序列 
		int right=-1;
		for (int j=mid+1;j<=num;j++)
		{
			if(x[j]==2)
			{
				right=j;break;
			}
		}//搜右边的可消除序列 
		if(right==-1&&left==-1)continue;
		else if(right==-1)ans+=num-left+1;
		else if(left==-1)ans+=right;
		else ans+=max(right-left+1,num/2 +1);
	}
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52