题意是给你一串首尾相连的珠子， 珠子有b r w三种颜色， 然后让你统计某两个珠子中间到两边相同珠子的最大数量是多少？？刚开始我选择了暴力求解， 后来看题解后有一种dp的方法， 感觉蛮赞的。。代码如下：
/* ID: m1500293 LANG: C++ PROG: beads */ #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 2*400 + 10; int len; char str[maxn]; int bl[maxn], br[maxn], rl[maxn], rr[maxn]; int main() { freopen("beads.in", "r", stdin); freopen("beads.out", "w", stdout); while(scanf("%d", &len) == 1) { scanf("%s", str+1); for(int i=len+1; i<=2*len; i++) str[i] = str[i-len]; bl[0] = rl[0] = 0; for(int i=1; i<=2*len; i++) { if(str[i] == 'r') rl[i]=rl[i-1]+1, bl[i]=0; if(str[i] == 'b') bl[i]=bl[i-1]+1, rl[i]=0; if(str[i] == 'w') bl[i]=bl[i-1]+1, rl[i]=rl[i-1]+1; } br[2*len+1] = rr[2*len+1] = 0; for(int i=2*len; i>=1; i--) { if(str[i] == 'r') rr[i] = rr[i+1]+1, br[i]=0; if(str[i] == 'b') br[i] = br[i+1]+1, rr[i]=0; if(str[i] == 'w') br[i]=br[i+1]+1, rr[i]=rr[i+1]+1; } int res = 0; for(int i=1; i<2*len; i++) { res = max(res, max(bl[i], rl[i])+max(br[i+1], rr[i+1])); } res = min(res, len); printf("%d ", res); } return 0; }