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

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

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

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

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

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

代码如下:

#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;
}