0525 Osenbei
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0525
方針
行数が最大10行までと小さいので、行のひっくり返し方を決めて全探索する。
行のひっくり返し方が決まれば、列の最適なひっくり返し方は一意に決まる。
ソース
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define REP(i,a,b) for(i=a; i<b; ++i) #define rep(i,n) REP(i,0,n) int board[10001]; int pop(int x) { int n = 0; while(x != 0) { n = n + 1; x &= (x-1); } return n; } int main() { int n,i,j,k,r,c; while(scanf("%d %d", &r, &c), r|c) { memset(board, 0, sizeof(board)); rep(i,r) { rep(j,c) { scanf("%d", &k); if(k) board[j] |= (1<<i); } } int ans = 0,tt,t; rep(i,(1<<r)) { t = 0; rep(j,c) { tt = pop(board[j] ^ i); t += max(tt, r-tt); } ans = max(ans, t); } printf("%d\n", ans); } }