torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #191, A : Flipping Game

概要

0 と 1 のみからなる n 項の数列が与えられる。
連続する項を反転する操作を丁度一回施すとき、操作後の 1 の数の最大でいくつか求めよ。

解法

反転させる区間の選び方を全通り試してシミュレーションしても O(n^3) で間に合うので全通り試します。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	int res = 0;
	REP( i, 0, n )
	{
		REP( j, i, n )
		{
			VI tmp( as );
			transform( tmp.begin() + i, tmp.begin() + j + 1, tmp.begin() + i, bind1st( minus<int>(), 1 ) );
			res = max( res, count( ALL( tmp ), 1 ) );
		}
	}

	cout << res << endl;

	return 0;
}