题解 P1203 【[USACO1.1]坏掉的项链Broken Necklace】

青衫白叙

2017-09-25 16:13:49

Solution

这绝对是最短的题解了。。。(难理解别打我。) 附上样例的输出以及中间结果来帮助理解: c a b w ans 0 1 1 0 0 2 2 0 0 3 3 0 b 0 4 0 3 b 0 5 0 3 r 5 1 0 5 r 5 2 1 5 r 5 3 0 5 b 3 1 0 8 r 1 1 0 8 b 1 1 0 8 r 1 1 0 8 r 1 2 0 8 b 2 1 0 8 r 1 1 0 8 b 1 1 0 8 r 1 1 0 8 r 1 2 1 8 r 1 3 0 8 r 1 4 1 8 r 1 5 2 8 r 1 6 0 8 b 6 1 0 8 b 6 2 1 8 r 1 2 0 8 r 1 3 1 8 r 1 4 0 8 r 1 5 0 8 b 5 1 0 8 b 5 2 1 8 b 5 3 2 8 b 5 4 3 8 b 5 5 0 8 b 5 6 0 8 r 6 1 0 11 r 6 2 1 11 r 6 3 0 11 b 3 1 0 11 r 1 1 0 11 b 1 1 0 11 r 1 1 0 11 r 1 2 0 11 b 2 1 0 11 r 1 1 0 11 b 1 1 0 11 r 1 1 0 11 r 1 2 1 11 r 1 3 0 11 r 1 4 1 11 r 1 5 2 11 r 1 6 0 11 b 6 1 0 11 b 6 2 1 11 r 1 2 0 11 r 1 3 1 11 r 1 4 0 11 r 1 5 0 11 b 5 1 0 11 11 c:当前处理的字符 a:从i向左最长的长度 b:从i向右最长的长度 w:当前w个数 我们知道:当b重新计算时,其实a已经算好了。。就是b-w(当前的w已经算在b里面了)(正着反着不是一样的吗) 而b重新计算时,又应该加上前面w的个数 好像没什么了。。。更新答案应该在b算完的时候。。a在上一轮已经算过了。。 ```cpp #include<cstring> #include<cstdio> #include<algorithm> using namespace std; char s[700],c; int a, b, w, ans; int main(){ int n; scanf("%d%s",&n,s); memcpy(s+n,s,n); //printf(" c a b w ans\n"); for(int i = 0; i < n<<1; i++) { if(s[i] == 'w') b++,w++;else if(s[i] == c ) b++,w=0;else ans=max(ans,a+b),a=b-w,b=w+1,w=0,c=s[i]; //printf("%2c %2d %2d %2d %2d\n",c,a,b,w,ans); } ans=max(ans,a+b); printf("%d\n",min(ans,n)); return 0; } ```