CFR 334 1A. Alternative Thinking ( DP )

Problem - 603A - Codeforces
dp[ i ][ j ][ k ]: considered i digits, not yet reversed / reversing / finished reversing, last digit is k

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;

int n;
int a[ MAXN ];

void upmax(int &x, int v){
    if( x < v ) x = v;
}

int dp[ MAXN ][ 3 ][ 2 ];

void solve(){
    dp[ 0 ][ 0 ][ 0 ] = dp[ 0 ][ 0 ][ 1 ] = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < 3; ++j)
            for(int k = 0; k < 2; ++k){
                upmax( dp[ i + 1 ][ j ][ k ], dp[ i ][ j ][ k ] );
                if( j == 0 ){
                    if( a[ i ] != k )
                        upmax( dp[ i + 1 ][ 0 ][ k ^ 1 ], dp[ i ][ j ][ k ] + 1 );
                    else
                        upmax( dp[ i + 1 ][ 1 ][ k ^ 1 ], dp[ i ][ j ][ k ] + 1 );
                } else if( j == 1 ){
                    if( a[ i ] ^ 1 != k )
                        upmax( dp[ i + 1 ][ 1 ][ k ^ 1 ], dp[ i ][ j ][ k ] + 1 );
                    else
                        upmax( dp[ i + 1 ][ 2 ][ k ^ 1 ], dp[ i ][ j ][ k ] + 1 );
                } else{
                    if( a[ i ] != k )
                        upmax( dp[ i + 1 ][ 2 ][ k ^ 1 ], dp[ i ][ j ][ k ] + 1 );
                }
            }
    int ans = 0;
    for(int j = 0; j < 3; ++j)
        for(int k = 0; k < 2; ++k)
            ans = max( ans, dp[ n ][ j ][ k ] );
    printf("%d\n", ans);
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%1d", &a[ i ]);
    solve();
    return 0;
}