首先顺序便利项链一次，计算出每个珠子向左能够延伸的最长距离
在便利到结尾的时候，比较项链的开始部分与最后结尾处的珠子种类，如果相同对项链前面的部分进行更新。
然后同样，倒叙相连一次，计算出每个珠子右向的最长距离
更新项链的最后部分
在做的过程中犯的错误：
（1）没有考虑如果一整个项链是一种珠子的情况
（2）例如bwrwrr中在，第一个r的时候其实前面的w的也应该算入r的左链的；但是如果从w后面断开的话，kw应该是一个链中的
因此我加入一个辅助数组wn（表示到位置i前有多少个w），如果遇到s[i-1]是w，而s[i]不是w的时候计算左链就用wn计算；
右链的计算同理。
感觉这样子计算用到的辅助数组比较多
#include <fstream>#include <iostream>#include <string>
using namespace std;
int main(){ ifstream fin("beads.in"); ofstream fout("beads.out"); int n;//珠子数目 string s;//项链 fin>>n>>s; int right[350] = {0}; int lef[350] = {0}; int wnl[350] = {0};//左数，w个数 int wnr[350] = {0};//右数，w个数 int bp[350] = {0};//分割点
char c = 0; int i;//循环 //找到左边的最大串 for (i = 0; i < n; i++) { //统计连续w的个数 if(i > 0 && s[i] == 'w' && s[i-1] == 'w') { wnl[i] = wnl[i-1] + 1; } //计算连续相同珠子的个数 if (s[i] == c || s[i] == 'w') { lef[i] = lef[i-1] + 1; } else { if(s[i-1] == 'w') { lef[i] = wnl[i-1] + 1; } } if('w' != s[i]) { c = s[i]; } //cout<<wnl[i]<<" "; } //根据最后一个珠子，更新开始的几个珠子 if (s[0] == c || s[0] == 'w') { lef[0] = lef[n-1] + 1; //cout<<endl<<lef[0]; int temp = 1; while ((temp <= n-1) && (s[temp] == c || s[temp] == 'w')) { lef[temp] = lef[temp-1] + 1; temp++; } } //找到右边的最大串 c = 0; for (i = n-1; i >= 0; i--) { //统计连续w的个数 if(i < n-1 && s[i] == 'w' && s[i+1] == 'w') { wnr[i] = wnr[i+1] + 1; }
if (s[i] == c || s[i] == 'w') { right[i] = right[i+1] + 1; } else { if(s[i+1] == 'w') { right[i] = wnr[i+1] +1; } } if('w' != s[i]) { c = s[i]; } } //根据第一个珠子，更细最后几个珠子 if (s[n-1] == c || s[n-1] == 'w') { right[n-1] = right[0] + 1; //cout<<right[n-1]; int temp = n-2; while (temp >= 0 && (s[temp] == c || s[temp] == 'w')) { right[temp] = right[temp+1] + 1; temp--; } } //最大点位置切开，珠子数目 int p = -1; for (i = 0; i < n; i++) { if (i == n-1) { bp[i] = lef[i] +right[0] + 2; } else { bp[i] = lef[i] + right[i+1] + 2; } if (bp[i] > p) { p = bp[i]; } //cout<<lef[i]<<" "<<right[i]<<endl; } //如果是纯色的珠子 if(p > n) p = n; fout<<p<<endl; //cout<<endl<<p<<endl; return 0;}
