概要
0 と 1 のみからなる n 項の数列が与えられる。
連続する項を反転する操作を丁度一回施すとき、操作後の 1 の数の最大でいくつか求めよ。
解法
反転させる区間の選び方を全通り試してシミュレーションしても で間に合うので全通り試します。
コード
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; }