丢手绢

题目链接：http://acm.ocrosoft.com/problem.php?cid=1629&pid=56

题目描述：

最近ACM集训队要做一个丢手绢游戏，有n个集训队员围成一圈准备开始游戏，这n个队员中有一部分人穿红色T恤，有一部分人穿绿色T恤，剩下的穿蓝色T恤，共三种颜色的T恤。悲惨的ZZY作为第一个丢手绢的人，有一个癖好，他不想看到两个穿相同颜色T恤的队员坐在一起。现在，ZZY希望聪明的你能帮他满足这个癖好，从这一圈队员中选出最少的人更换衣服（衣服只有红、绿、蓝三种颜色的），使得这一圈队员中任何相邻的两个人都穿不同颜色的衣服。两个人之间没有其它人就是相邻。

输入

先输入一个T（0<T<=10000）,表示下面有T组测试数据。

每组测试包括两行。

第一行为一个整数n(1≤n≤100)，表示有n个集训队员围成一圈。

第二行为一串字符串s，表示这n个队员的T恤颜色。这n个队员从1到n编号。如果第i个字符为R表示第i号队员穿红色T恤，如果第i个字符为G表示第i号队员穿绿色T恤，如果第i个字符为B表示第i号队员穿蓝色T恤。

输出

对于每组输入数据，先输出单独一行"Case #i:"（其中i表示第i组测试数据，从1开始），下一行再输出需要更换衣服的最少人数。

样例输入：

3
3
RRG
5
RRRRR
4
BRBG

样例输入：

Case #1:
1
Case #2:
3
Case #3:
0

思路：

化环为链，不需要用动态规划，数学分析就行，输入相同颜色的时记录长度，比如RRBBGGR，记录2 2 2 1,如果首位一样则首位长度相加，变成3 2 2，每长度除以2向下取整相加就是答案。（若整个环颜色一模一样，奇数除2向上取整，偶数直接除以二）

代码：

#include<bits/stdc++.h>
using namespace std;
int dp[1000];
char a[1000];
int main()
{
	int t;
	cin >> t;
	for (int k = 1; k <= t; k++)
	{
		memset(dp, 0, sizeof(dp));
		int n;
		cin >> n;
		cin >> a;
		int x = 0;//记录每个相同颜***带的长度
		int xx = 0;//记录整个环由几条色带组成
		int fla = 0;//判断整个环是否是同一种颜色
		for (int i = 0; i < n; i++)
		{
			x++;
			if (a[i] != a[i + 1])
			{
				if (i != n - 1)
				{
					fla = 1;
				}
				dp[xx++] = x;
				x = 0;//赋值后长度初始化
			}
		}
		if (a[0] == a[n - 1])//若首尾颜色相同则色带长度相加
		{
			dp[0] += dp[xx - 1];
			dp[xx - 1] = 0;
		}
		if (fla == 0)//若整个环颜色相同
		{
			if (n % 2 == 0||n == 1)//偶数或整个环就1个人。。。
			{
				cout << "Case #" << k << ":" << endl;
				cout << n / 2 << endl;
			}
			else
			{
				cout << "Case #" << k << ":" << endl;
				cout << n / 2 + 1 << endl;
			}
		}
		else//整个环的颜色大于等于两种
		{
			int sum = 0;
			for (int i = 0; i < xx; i++)
			{
				sum += dp[i] / 2;
			}
			cout << "Case #" << k << ":" << endl;
			cout << sum << endl;
		}
	}
}