Volume 5 / 0525
情報オリンピック 2007予選 解答
Problem 0525 : Osenbei
公式の解説のまんま。
#include <iostream> #include <vector> using namespace std; // 数え上げ int countUp( vector< vector<int> > src ) { int i, j, cnt, result = 0; for( j=0; j<src[0].size(); j++ ){ cnt = 0; for( i=0; i<src.size(); i++ ) if( src[i][j] ) cnt++; result += ( cnt > src.size()-cnt ) ? cnt : src.size()-cnt; } return result; } // ひっくり返す行の組み合わせを全て試す int solve( vector< vector<int> > src, int x ) { int max, new_val, i; for( i=0; i<src[x].size(); i++ ) src[x][i] = (src[x][i]+1)%2; max = countUp( src ); for( i=x+1; i<src.size(); i++ ){ new_val = solve( src, i ); if( max < new_val ) max = new_val; } return max; } int main(void) { int r, c, input, i, j, max, new_val; vector< vector<int> > senbei; while( cin >> r >> c, r != 0 ){ senbei.clear(); senbei.resize(r); for( i=0; i<r; i++ ){ for( j=0; j<c; j++ ){ cin >> input; senbei[i].push_back(input); } } max = countUp(senbei); for( i=0; i<senbei.size(); i++ ){ new_val = solve( senbei, i ); if( max < new_val ) max = new_val; } cout << max << endl; } return 0; }