Codeforces 877B Nikita and string 暴力简单题= =

One day Nikita found the string containing letters "a" and "b" only.

Nikita thinks that string is beautiful if it can be cut into 3 strings (possibly empty) without changing the order of the letters, where the 1-st and the 3-rd one contain only letters "a" and the 2-nd contains only letters "b".

Nikita wants to make the string beautiful by removing some (possibly none) of its characters, but without changing their order. What is the maximum length of the string he can get?

Input

The first line contains a non-empty string of length not greater than 5 000 containing only lowercase English letters "a" and "b".

Output

Print a single integer — the maximum possible size of beautiful string Nikita can get.

Examples

input

abba

output

input

bab

output

Note

It the first sample the string is already beautiful.

In the second sample he needs to delete one of "b" to make it beautiful.

来源： http://codeforces.com/contest/877/problem/B

题意：给出一个字符串，这个字符串长度最大是5000，并且规定只有ab组成，现在问你，能不能将这个字符串分成三部分，第一和第三部分只有a或者是空，第二部分由b或者空组成。问你能不能分成这样的形式，如果能那么最长的长度是多少。

思路：就是一个暴力题，但是就是没有想到要暴力的去做。很明显要组成这样的形式一共是有5种情况的。

分别是a,b,ab,ba,aba。那么我们只要统计出这五种情况的最大的长度，最后我们取其中最大的就好了。那么如何处理出这五种可能的最大值呢。那就是暴力了。很简单的。

1.a/b

这个和只有b是一样的，那就是直接统计这个字符串中ab的个数就好了

2.ab/ba

这两种情况也是比较的简单的，那就是要明白如果是ab的话，那么意味这前面只有a，每次遇到一个b，就只算最大值，这样就可以得出最大值是多少了。

3.aba

这种是比较蛋疼的一种了，但是也很简单，那就是看成两部分，一部分求ab的最大值，一部分求ba的最大值。然后加起来就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int maxn=100000+10;
const int mod=1e9+7;
struct point
{
    int a;
    int b;
};
point aa[10000];
string s;
int bb[5];
void init(int num)
{
    int i,j,k;
    int flag_a=0,flag_b=0;
    for(i=0;i<num;i++)
    {
        if(s[i]=='a')
        {
            if(flag_a==0)
            {
                aa[i].a=1;
                flag_a=1;
            }
            else
            {
               aa[i].a=aa[i-1].a+1;
            }
            aa[i].b=aa[i-1].b;
        }
        if(s[i]=='b')
        {
            if(flag_b==0)
            {
                aa[i].b=1;
                flag_b=1;
            }
            else
            {
                aa[i].b=aa[i-1].b+1;
            }
            aa[i].a=aa[i-1].a;
        }
    }
    bb[0]=aa[num-1].a;
    bb[1]=aa[num-1].b;
    int max_x=-100,max_i;
    for(i=0;i<num;i++)
    {
        if(s[i]=='b')
        {
            int num1=aa[i].a;
            num1+=aa[num-1].b-aa[i].b+1;
            if(num1>max_x)
            {
                max_x=num1;
            }
        }
    }
    bb[2]=max_x;
    max_x=-1000;
    for(i=0;i<num;i++)
    {
        if(s[i]=='a')
        {
            int num1=aa[i].b;
            num1+=aa[num-1].a-aa[i].a+1;
            if(num1>max_x)
            {
                max_x=num1;
            }
        }
    }
    bb[3]=max_x;
    max_x=-100;
    int max_x2=-100;
    int max_x3=-1000;
    for(i=0;i<num;i++)
    {
       max_x=-100;
       max_x2=-100;
       for(j=0;j<=i;j++)
       {
           if(s[j]=='b')
           {
              int num1=aa[j].a;
              num1+=aa[i].b-aa[j].b+1;
              if(num1>max_x)
              {
                  max_x=num1;
              }
           }
       }
       for(j=i+1;j<num;j++)
       {
           if(s[j]=='a')
           {
               int num1=aa[j].b-aa[i].b;
               num1+=aa[num-1].a-aa[j].a+1;
               if(num1>max_x2)
               {
                   max_x2=num1;
               }
           }
       }
       if(max_x>=2&&max_x2>=2)
       {
           max_x+=max_x2;
           if(max_x>max_x3)
           {
               max_x3=max_x;
           }
       }
    }
    bb[4]=max_x3;
}
int main()
{
    cin>>s;
    int i,j,k;
    memset(bb,0,sizeof(bb));
    int num=s.size();
    init(num);
    int max_x=-1000;
    for(i=0;i<5;i++)
    {
        if(bb[i]>max_x)
        {
            max_x=bb[i];
        }
    }
    printf("%d
",max_x);
    return 0;
}