将红色的设置为-1,绿色的为1,统计前缀和sum,如果sum[i] == sum[j],则说明i~j是一个稳定的区间
因为答案要求最大,所以我们要记录每个sum值的最左端点(也就是哪个位置第一次出现某个sum值)
每当遇到某个sum值,便利用最左端点求出区间长度,更新答案
吐槽:洛谷标签里是个DP,我就没往其他方面考虑,实在想不出来看了一下题解,tm我信你个鬼,这tm算DP?******(some bad words)反正我不认为这是个DP
最终结论:我太菜了......
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 5 using namespace std; 6 7 string l; 8 int pos[2000006],sum[2000006],ans; 9 10 inline int max(int a,int b) { 11 if(a >= b) return a; 12 return b; 13 } 14 15 inline int min(int a,int b) { 16 if(a >= b) return b; 17 return a; 18 } 19 20 int main() { 21 cin >> l; 22 int len = l.length(); 23 for(int i = 1;i <= len; i++) 24 if(l[i-1] == ‘R‘) sum[i] = -1; 25 else sum[i] = 1; 26 memset(pos,0x3f3f3f,sizeof(pos)); 27 pos[len] = 0; 28 for(int i = 1;i <= len; i++) { 29 sum[i] += sum[i-1]; 30 pos[sum[i]+len] = min(i,pos[sum[i]+len]); 31 ans = max(ans,i - pos[sum[i]+len]); 32 } 33 printf("%d",ans); 34 return 0; 35 }
原文：https://www.cnblogs.com/lipeiyi520/p/12293358.html