Codeforces Round #442 (Div. 2) B. Nikita and string

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define maxn 505
 7 using namespace std;
 8 int main(){
 9     char a[5001];
10     int b[5001],c[5001];
11     cin>>a+1;
12     int t=strlen(a+1);
13     for(int i=1;i<=t;i++){
14         b[i]=b[i-1]+(a[i]=='a');//前i个a的个数
15         c[i]=c[i-1]+(a[i]=='b');//前i个b的个数
16     }
17     int ans=0;
18     for(int i=0;i<=t;i++){//为什么不从1开始，因为aba有空串情况
19         for(int j=i;j<=t;j++){
20             ans=max(ans,b[i]+c[j]-c[i]+b[t]-b[j]);//(前i个a的个数)+(i到j的b的个数)+(j到t的a的个数)
21         }
22     }
23     cout<<ans;
24     return 0;
25 }