题意:一串项链,由三种颜色r、w、b组成,w可以任意变成r或b,然后从某一点切开,分别从切开处向里面数同一种颜色的珠子,直到碰到不同颜色停止,问最多有多少颗珠子。
思路:一道比较有意思的字符串题目,主要就是w,可以变成左边字母也可以变成右边字母,做完看analysis似乎有用DP的方法,略屌。
代码在运算符之间加了些空格准备慢慢适应这种写法。。
/* ID: zz401 LANG: C++ TASK: beads */ #include<iostream> #include<fstream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; char str1[400],str2[800]; int main () { freopen ("beads.in", "r", stdin); freopen ("beads.out", "w", stdout); int n, i, wsum = 0, a = 0, b = 0, maxm = 0; //b是加上w变色一种颜色的总和,a是不加w变色的一种颜色的总和 char temp; cin>>n; cin>>str1; strcpy(str2,str1); strcat(str2,str1); temp=0; //temp记录b或r,初始随便一个非b、r、w即可 for(i=1;i<2*n;i++){ if(str2[i]=='w'){ b++; wsum++; } else if(str2[i]==temp){ b++; wsum = 0; } else{ if(a + b > maxm) maxm = a + b; a = b - wsum; b = wsum + 1; wsum = 0; temp = str2[i]; } } if(a + b > maxm) maxm = a + b; if(maxm > n) maxm = n; //需要判断,防止字符串全是一个字母的情况 cout<<maxm<<endl; return 0; }