mayoko’s diary

プロコンとかいろいろ。

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;
}