Codeforces #191 Div2 A "Flipping Game"
問題
http://codeforces.com/contest/327/problem/A
訳
ラハブは退屈しのぎに紙を使って遊ぶゲームを考えた。
彼はa1, a2, ..., anのn個の整数を書いた。各整数は0か1のどちらかである。彼は1回だけ次のような操作を行う。彼は2つのインデックスiとj(1 <= i <= j <= n)を選び、インデックス[i, j]の範囲の、全ての整数をフリップする。値xをフリップするとは、x = 1 - xとすることを意味する。
上記の操作を行った後の、1の数を最大化せよ。
制約
1 <= n <= 100
チュートリアルを見て
O(n)でやる方法がわからん・・・
しょうがない、O(n^3)でやろう
ソースコード
int main() { int N; int a[110]; cin >> N; for( int i = 0; i < N; i++ ){ cin >> a[i]; } int ans = 0; for( int l = 0; l < N; l++ ){ for( int r = l; r < N; r++ ){ int b[110]; memcpy( b, a, sizeof(a) ); for( int i = l; i <= r; i++ ){ b[i] = 1 - b[i]; } int res = 0; for( int i = 0; i < N; i++ ){ res += b[i]; } ans = max( ans, res ); } } cout << ans << endl; }