CFR 327 A. Flipping Game ( DP )

Problem - 327A - Codeforces
題意：
給一串 0 或 1 組成的序列，接著必須取一段連續的子序列將 0 和 1 皆反轉。求最長可能連續 1 的長度。
解法：
dp[ i ][ j ] : 考慮序列中前 i 個值，還沒翻 / 正在翻 / 翻完了，時的最長長度。

int N;
vi A;

void init(){
	cin >> N;
	A = vi( N );
	for( int i = 0; i < N; ++i )
		cin >> A[ i ];
}

void preprocess(){

}

void solve(){
	vvi dp( N + 1, vi( 3, -INF ) );
	dp[ 0 ][ 0 ] = 0;
	for( int i = 0; i < N; ++i ){
		upmax( dp[ i + 1 ][ 0 ], dp[ i ][ 0 ] + A[ i ] );
		upmax( dp[ i + 1 ][ 1 ], dp[ i ][ 0 ] + !A[ i ] );
		upmax( dp[ i + 1 ][ 1 ], dp[ i ][ 1 ] + !A[ i ] );
		upmax( dp[ i + 1 ][ 2 ], dp[ i ][ 1 ] + A[ i ] );
		upmax( dp[ i + 1 ][ 2 ], dp[ i ][ 2 ] + A[ i ] );
	}
	cout << max( dp[ N ][ 1 ], dp[ N ][ 2 ] ) << endl;
}