r[0] = p[0] = 0
If c = 'r' then r[p+1] = r[p] + 1 and b[p+1] = 0
because the length of the blue beads is 0.
if c = 'b' then b[p+1] = b[p] + 1 and r[p+1] = 0
if c = 'w' then both length of the red and length of blue beads
can be longer.
so r[p+1] = r[p]+1 and b[p+1] = b[p] + 1.
The number of beads that can be collected in breaking point p
is then max(left[r[p]], left[b[p]]) + max(right[r[p]], right[b[p]]).
And the maximum from this value is answer for the problem.
/*
ID:chsc4691
LANG:C++
PROB:beads
*/
#include <fstream>
using namespace std;
ifstream cin( "beads.in" );
ofstream cout( "beads.out" );
string necklace;
int leftt[800][2];
int rightt[800][2];
int n, ans;
void
__read__()
{
cin >> n
>> necklace;
}
void
__precalc__()
{
necklace += necklace;
for( int i = 1; i <= n * 2; i++ )
{
if( necklace[i - 1] == 'r' )
{
leftt[i][0] = leftt[i - 1][0] + 1;
leftt[i][1] = 0;
}
if( necklace[i - 1] == 'b' )
{
leftt[i][1] = leftt[i - 1][1] + 1;
leftt[i][0] = 0;
}
if( necklace[i - 1] == 'w' )
{
leftt[i][0] = leftt[i - 1][0] + 1;
leftt[i][1] = leftt[i - 1][1] + 1;
}
}
for( int i = n * 2 - 1; i >= 0; i-- )
{
if( necklace[i] == 'r' )
{
rightt[i][0] = rightt[i + 1][0] + 1;
rightt[i][1] = 0;
}
if( necklace[i] == 'b' )
{
rightt[i][1] = rightt[i + 1][1] + 1;
rightt[i][0] = 0;
}
if( necklace[i] == 'w' )
{
rightt[i][1] = rightt[i + 1][1] + 1;
rightt[i][0] = rightt[i + 1][0] + 1;
}
}
}
int
max( int x, int y )
{
if( x > y )
return x;
else
return y;
}
void
__dp__()
{
for( int i = 1; i <= n * 2; i++ )
ans = max( ans, max( leftt[i][0], leftt[i][1] ) + max( rightt[i][0], rightt[i][1] ) );
if( ans > n )
ans = n;
}
void
__outp__()
{
cout << ans << endl;
}
int
main()
{
__read__();
__precalc__();
__dp__();
__outp__();
return 0;
}
|