7-4 1.1.4 破碎的项链 (80分) 你有一条由 N 个红色的,白色的,或蓝色的珠子组成的项链(3<=N<=350),珠子是随意安排的. 这里 是 n=29 的二个例子 : 第一和第二个珠子在图片中已经被作记号. 图片 A 中的项链可以用下面的字符串表示: brbrrrbbbrrrrrbrrbbrbbbbrrrrb . 假如你要在一些点打破项链,展开成一条直线,然后从一端开始收集同颜色的珠子直到你遇到一个 不同的颜色珠子,在另一端做同样的事.(颜色可能与在这之前收集的不同) 确定应该在哪里打破项链来收集到最大数目的珠子.
Example 在图片 A 中的项链,可以收集到 8 个珠子, 在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链. 在一些项链中,包括白色的珠子如图片 B 所示. 当收集珠子的时候,一个被遇到的白色珠子可以被当做红色也可以被当做蓝色. 表现项链的字符串将会包括三符号 r , b 和 w .
写一个程序来确定从一条项链最大可以被收集的珠子的数目.
输入格式: 第 1 行: N, 珠子的数目 第 2 行: 一串度为 N 的字符串, 每个字符是 r , b 或 w.
输出格式: 单独的一行包含从被供应的项链可以被收集的珠子数目的大值.
输入样例1: 在这里给出一组输入。例如：
29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
输出样例1: 在这里给出相应的输出。例如：
11
输入样例2:
6 wwwwww
输出样例2:
6
输入样例3:
6 rrrbbb
输出样例3:
6
【题意】
【思路】
【源代码】
#include <iostream> #include <algorithm> using namespace std; int Length(const int n, string* s) // 在n,(n+1)之间断开得到的长度； { int len = 0; for (int i = n;; i--) // 往前看，得到断点前的长度； { if ((*s)[i] == (*s)[n]) // 遇上相同颜色； { len++; } else if ((*s)[i] == 'w') // 遇上白色珠子，同化； { len++; } else { break; } } for (int i = (n + 1);; i++) // 往后看，得到断点后的长度； { if ((*s)[i] == (*s)[n + 1]) // 遇上相同颜色； { len++; } else if ((*s)[i] == 'w') // 遇上白色珠子，同化； { len++; } else { break; } } return len; } int main() { int ans = -1; // 所求的最大长度； int n; cin >> n; string str = ""; cin >> str; str = str + str + str; // 将项链按顺序复制成三段，前段，原段，末段； for (int i = n; i < (2 * n); i++) // 从原段开始处理； { if (str[i] == str[i + 1]) { continue; } if (str[i] == 'w') { str[i] = 'r'; ans = max(ans, Length(i, &str)); // 'w'作为'r'时的长度； str[i] = 'b'; ans = max(ans, Length(i, &str)); // 'w'作为'b'时的长度； str[i] = 'w'; // 保证数据没有被修改； } ans = max(ans, Length(i, &str)); // 及时更新最长的长度； } ans = min(ans, n); // 最长长度<=原项链的总长; if (ans == -1) // 项链上的珠子全为同一种颜色； { ans = n; } cout << ans << endl; return 0; }