题目做一个简单的介绍，有一串项链，有三种颜色组成，分别是白色、红色和蓝色，用字母w、r、b代替，从某一个位置切断，输入这个断掉项链，然后让你找到一个断点，使这 个断点开始左右两边的最长连续颜色最长，遇到不同的颜色就要终止，w可以代表红色也可以代表蓝色，就是找到这样的一个断点。

这道题，感觉和动态规划没有什么关系，看别人做的基本上也没有什么状态转移方程，或者我感觉那不是状态转移方程。有这样一个思路，就是列举每一个分割点，然后求出每个断点的左 右两边的最长连续的颜色之和，找出一个最大值，那么这个断点也就是找到了，但是我觉得这个方法有可能会超时的，这个就相当于枚举法了。当数据量大的时候，这个方法是行不通的。 可是，这个标签是有动态规划，实在是想不到有什么动态可以用的上。

中间我想到了一个这样的方法，就是把连续长度的颜色转换成数字，然后存放到一个数组中，但是这样处理有了一个问题，w不好处理，假如只有红色和蓝色，我只需要保正头和尾不一样 就可以了，转换成数组直接求连个相邻的数最大值就可以，但是很无奈，又多出了一个白色，当位于两种相同颜色之间的时候，那这个w别无选择，只能够等于这种颜色，当位两种于不同颜色之间的时候，该选哪个呢？尤其是连续w的时候，我觉得很难处理。

最后看到了一个别人写的时间复杂度为O(n)的一种解法，觉得很好。他是这样考虑的，也是相当于一个一个遍历每一个切割点，为了处理好项链是一个环的问题，又在这个字符串的后面加上了这个字符串，设置几个变量：w,L,R,c,Max,w代表白色珠子的连续长度，c代表当前处理的字符,l代表当前字符左边最长的连续颜色相同的珠子,r代表当前字符右边最长连续颜色相同的珠子,Max代表每个断点左右两边L和R之和的最大值。

整个程序就是依靠于R（向右走），当遇到w时，不论右边是红色还是都是可以相连的，所以w和R都可以加一，当遇到字符的颜色和当前处理的字符相同的时候，w就需要归0了，而R还可以继续往上加，当遇到两个不同的字符的时候，就需要对一些值进行更新了，这个实际上每次是对上一个字符左右的最大值进行更新，因为第一个字符的右边就相当于第二个字符的左边，将整个项链的左右进行更新，从前到后，遍历每一个断点，但是这样处理会出现一个问题，就是当所有的珠子都为白色的时候，那么能取到项链的最大值会是n的二倍，超过了n，所以要在算最后结果的时候要排除这样的情况，在Max和n之间取一个最小值。

这到底是动规吗？有点像数论规律题。

代码如下：

 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

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int l = 0;//当前字符左边的的最大连续颜色相等的珠子数
int r = 0; //当前字符右边的的最大连续颜色相等的珠子数
int w = 0;//白色珠子的最大连续数
int c = 'x';//代表当前需要处理的字符
int Max = -1;//最终结果
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = s + s;
    for (int i = 0; i < 2 * n; i++)
    {
        if (s[i] == 'w')
        {
            w++;
            r++;
        }
        else if (s[i] == c)
        {
            r++;
            w = 0;
        }
        else
        {
            Max = max(Max, l + r);
            l = r - w;
            r = w + 1;
            w = 0;
            c = s[i];
        }
    }
    Max = max(Max, l + r);
    cout << min(Max, n);
    return 0;
}