题意:有一个烤饼器可以烤r行c列的煎饼,煎饼可以正面朝上(用1表示)也可以背面朝上(用0表示)。一次可将同一行或同一列的煎饼全部翻转。现在需要把尽可能多的煎饼翻成正面朝上,问最多能使多少煎饼正面朝上?
输入:多组输入,每组第一行为二整数r, c (1 ≤ r ≤ 10, 1 ≤ c ≤ 10 000),剩下r行c列表示煎饼初始状态。r=c=0表示输入结束。
输出:对于每组输入,输出最多能使多少煎饼正面朝上。
(翻译参考自:http://bbs.byr.cn/#!article/ACM_ICPC/73337?au=Milrivel)
分析:这个是二维的穷举,因为列数比较多行数比较少,所以可对行做深度优先遍历穷举所有行的情况。这里用bitset保存每一行的情况,对于行的翻装,只需要用自带的flip函数。对于每一行都确定动作时,统计每一列翻时会出现的正面朝上的值以及不翻时的值,取较大数。此时为行动作确定时,列动作可以做到的最优值。因此穷举所有行情况即可求出实际最优值。
#include <cstdio>
#include <algorithm>
#include <bitset> using namespace std; const int MAX_R = ;
const int MAX_C = ; //input
int R, C;
bitset<MAX_C> a[MAX_R]; int ans; void dfs(int k){
if(k == R){
//row certain
int result = ; //cur max value
for(int j = ; j < C; j ++){
int upNum = ; //up numbers without fliping
for(int i = ; i < R; i ++){
if(a[i][j]) upNum ++;
}
result += max(upNum, R - upNum);
}
ans = max(ans, result);
return;
}
//without fliping
dfs(k + );
//·flip
a[k].flip();
dfs(k + ); a[k].flip();
} void solve(){
ans = ;
dfs();
printf("%d\n", ans);
} int main(int argc, char const *argv[]){ while(scanf("%d %d", &R, &C)){
if(R == && C == ) break; for(int i = ; i < R; i ++){
for(int j = ; j < C; j ++){
bool tmp;
scanf("%d", &tmp);
a[i][j] = tmp;
}
}
solve();
} return ;
}