[USACO][Section 1.1][贪心] Broken Necklace

题目大意：

给出一个字符串，包含‘r’、‘w’、‘b’三种字符。将字符串首尾相连，需要求出r…rb…b或b…br…r这种形式的子串的长度最大为多少。其中字符‘w’可以随意充当另外两种字符。

思路：

本题在求解过程中使用了贪心思想。 对于给出的字符串（暂时不考虑字符串中的字符全部相同的情况，此情况下直接输出字符串长度即可），可以将其分解为不同的子串r…rb…b或b…br…r（此时‘w’充当了其它两种字符串）。 那么现在就可以将问题分成两种情况进行讨论： 1.最长子串是r…rb…b的形式。 2.最长子串是b…br…r的形式。 不管哪种情况，最长子串都可以分为两个连续部分，其中一部分全是字符‘r’，简称r部，另一部分全是字符‘b’，简称b部。

接下来运用到了贪心思想。 可以想象到，对于最长子串来说，r部、b部都应尽可能的长。例如rrbbbrb的最长子串为rrbbb，其r部和b部都在条件范围内尽可能的伸展到最大。 这个结论是解题的关键。引出了本题的核心思想： 对于一个给出的字符串，找出所有的子串rb与br，并将这些子串的r部与b部延伸至最大。子串r部与b部之和的最大值就是所求答案。

下面我们针对“最长子串是r…rb…b的形式”这种情况进行详细解释。 建立两个数组r[]、b[]。 其中r[i]表示从字符串的位置i开始向左延伸的r部最大长度。 b[i]表示从字符串的位置i开始向左延伸的b部最大长度。 在初始化r[]的过程中，字符串‘w’全部充当为‘r’。 同理，在初始化b[]的过程中，字符串‘w’全部充当为‘b’。

接着，我们对字符串进行遍历，找出所有的子串rb，并求出其延伸后的长度。 举例来说，有一个字符串片段…b(rrrbbb)r…其中括号内是一个无法延伸的子串。 假设字符串片段中最右侧的字符‘r’在字符串内的位置为i。 那么括号内子串的b部长度则为b[i-1]，r部长度为r[i-b[i-1]-1]。r部与b部之和即为括号内子串的长度。 按此方法可以求出所有r…rb…b形式子串的长度。与其类似，再求出所有b…br…r形式子串的长度，其中最大值即为答案。

代码：

/*
ID: lujunda1
LANG: C++
PROG: beads
*/
#include
#include
#include
#include
using namespace std;
#define datasize 10000
char necklace[datasize],temp_r[datasize],temp_b[datasize];
int len,r[datasize],b[datasize];
int init()
{
    strcpy(temp_r,necklace);
    strcpy(temp_b,necklace);
    //将‘w’全部转换为‘r’或‘b’。 
    for(int i=0;i>len>>necklace;
    init();
    //判断一个字符串是否只有除‘w’以外的一种字符。 
    if(check(temp_r)&&check(temp_b))
    {
        cout<temp_max?max:temp_max;
        }
        if(temp_b[i]=='r'&&temp_b[(len+i-1)%len]=='b')
        {
            int temp_max=r[(len+i-b[(len+i-1)%len]-2)%len]+b[(len+i-1)%len]+2;
            max=max>temp_max?max:temp_max;
        }
    }
    //在上述计算过程中，在字符串本身就是其最大子串的情况下，max的值可能大于len。此时直接输出len即可。 
    if(max<=len)
        cout<