AOJ 2546: Chocolate
解法
まず, チョコレートを取る順番は上の行から順番で良いとわかります。これは 2 行目以降のチョコレートは必ずそれより上にあるチョコレートを取らないと取ることが出来ないことからわかります。
ということで, 一番上の行はそのままの状態で考えて, それ以降の行は上の行を取ってから取り始めるので, 元の状態から反転しています。
後は各行について, どういうふうに取るのが最適かを考えます。
各チョコレートは, 左端と右端は 0/1 回反転し, それ以外のチョコレートは 1/2 回反転します。
基本的には前者で 1 回反転するチョコレートはひとつだけで, 後者で 2 回反転するのも 1 つだけです。
それを上手いこと場合分けしましょう。
const int MAXN = 101; int a[MAXN][MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int M, N; cin >> M >> N; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { cin >> a[i][j]; if (i > 0) a[i][j] ^= 1; } } int ans = 0; if (N == 1) { for (int i = 0; i < M; i++) { ans += a[i][0]; } cout << ans << endl; return 0; } else { for (int i = 0; i < M; i++) { int maxi = 0; // 左端 0, 右端 1 { int tmp = a[i][0]; for (int j = 1; j < N; j++) { tmp += (a[i][j]^1); } maxi = max(maxi, tmp); } // 右端 0, 左端 1 { int tmp = a[i][N-1]; for (int j = N-2; j >= 0; j--) { tmp += (a[i][j]^1); } maxi = max(maxi, tmp); } // どっちも 0 if (N > 2) { int tmp = a[i][0] + a[i][N-1]; bool ok = false; for (int j = 1; j < N-1; j++) { if (a[i][j] == 1) ok = true; } if (ok) { tmp += 1; for (int j = 1; j < N-1; j++) { if (a[i][j] == 0) tmp++; } maxi = max(maxi, tmp); } } ans += maxi; } cout << ans << endl; } return 0; }