スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

AOJ 0525 Osenbei

0の個数を最大にするとき、どの行をひっくり返すか決めると
ひっくり返すべき列とそれで得られる0の個数が一意的に決まる。
Rが十分に小さいので行のひっくり返し方を全通り試し
そのひっくり返し方に対応する0の個数の最大を出力する。
行のひっくり返し方を再帰で書くとこんな感じ

int senbei[10][10000];
int r,c;
int rowFlag[10];
int Max;

void countSum(){
int sum=0;
for(int i=0;i int colSum = 0;
for(int j=0;j if(senbei[j][i]==!rowFlag[j]){
colSum++;
}
}
sum += max(colSum,r-colSum);
}
if(Max Max = sum;
}
}

void setFlag(int pos){
if(pos==r){
countSum();
return;
}
rowFlag[pos] = 1;
setFlag(pos+1);

rowFlag[pos] = 0;
setFlag(pos+1);
}

int main(){
while(1){
cin >> r >> c;
if(r==0&&c==0) return 0;
for(int i=0;i for(int j=0;j cin >> senbei[i][j];
}
}
Max = 0;
setFlag(0);
cout << Max << endl;
}
}




再帰を使わないで蟻本っぽく解くならこんな感じ?
通ったから一応あってると思う。


int senbei[10][10000];
int r,c;
int rowFlag[10];
int Max;

int countSum(){
int sum=0;
for(int i=0;i int colSum = 0;
for(int j=0;j if(senbei[j][i]==!rowFlag[j]){
colSum++;
}
}
sum += max(colSum,r-colSum);
}
return sum;
}

int main(){
while(1){
cin >> r >> c;
if(r==0&&c==0) return 0;
for(int i=0;i for(int j=0;j cin >> senbei[i][j];
}
}
Max = 0;
for(int i=0;i<1< for(int j=0;j rowFlag[j] = i >> j & 1;
}
int sum = countSum();
if(Max Max = sum;
}
}
cout << Max << endl;
}
}


コメントの投稿

非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。