洛谷P2697 宝石串

 1 #include <bits/stdc++.h> 
 2 #define For(i,j,k) for(int i=j;i<=k;i++) 
 3 using namespace std ; 
 4 
 5 const int N = 1000011,inf = 1e9 ; 
 6 int n,ans ; 
 7 char s[N] ; 
 8 int sum[N],t[N],l[N],tt[N],r[N]  ; 
 9 
10 inline int read() 
11 {
12     int x = 0 , f = 1 ; 
13     char ch = getchar() ; 
14     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 
15     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 
16     return x * f ;  
17 }
18 
19 int main() 
20 {
21     scanf("%s",s+1) ; 
22     n = strlen(s+1) ; 
23     For(i,1,n) 
24         sum[ i ]=sum[i-1]+((s[i]=='R')?-1:1) ;  
25     For(i,-N,N) l[ i ]=N ; 
26     l[ 0 ] = 0 ; 
27     For(i,1,n) {
28         if(l[ sum[i] ]==N) l[sum[i]] = i ; 
29         r[sum[i]] = i ; 
30     }
31     ans = 0 ; 
32     For(i,-n,n) 
33         if( r[i]-l[i]>ans ) ans = r[i]-l[i] ; 
34     printf("%d
",ans) ; 
35     return 0 ; 
36 }