AOJ0525

深さ優先探索お煎餅を行で裏返すか裏返さないか、$2^R$回探索するだけ。色々考えた結果、裏返さない場合と裏返す場合の煎餅の並びを先に計算しておいて、各行について裏返すか裏返さないかのフラグを入れていった。

深さ優先探索は最深部に辿りついてから処理すればいいのね。

ところで、複数データセットがある場合ってデータセットが入力されるごとに出力してもいいんですかね？

解答時間は50分でした。

以下コードです。

#include <stdio.h>
#include <algorithm>

int field[10][2][10000];
int h,w;
int col_sum;
int sum = 0;
int now_sum = 0;
int ans[5];
int n = 0;
int sel[10];


void all(int k){
  if(k != h){
    sel[k] = 0;
    all(k+1);
    sel[k] = 1;
    all(k+1);
  }
  now_sum = 0;
  for(int j = 0; j < w; j++){
    col_sum = 0;
    for(int i = 0; i < h; i++){
      col_sum += field[i][sel[i]][j];
    }
    now_sum += std::max(col_sum,h-col_sum);
  }
  sum = std::max(now_sum,sum);
}

int solve(){
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      field[i][1][j] = (field[i][0][j] + 1) % 2;
    }
  }
  sum = 0;
  all(0);
  return sum;
}

int main(){
  while(true){
    scanf("%d %d",&h, &w);
    if(h == 0 && w == 0)
      break;
    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
        scanf("%d", &field[i][0][j]);
      }
    }
    ans[n++] = solve();
  }
  for(int i = 0; i < n; i++){
    printf("%d\n", ans[i]);
  }
  return 0;
}

ただの院生

ただの院生の日記的な

AOJ0525

AOJ0525