AOJ 0525 Osenbei

 由于n比较小，所以可以对行DFS，那列呢？其实列很好处理，对每一列统计1的个数或者0的个数，保留最大者即是最大的正面个数，试想如果当前列正面个数多，那这一列就不翻面就好了，如果反面多，那么将该列翻面即可使得原先反面变成正面。所以对列直接统计即可。

 这题需要注意的是无论哪一行或者那一列先翻面都是无谓的，不影响结果，即翻面的顺序不影响结果，只考虑该行或该列是否要翻面即可，所以可以直接DFS。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4
 5 using namespace std;
 6
 7 int r,c;
 8 int maze[15][10005];
 9 int maxRes;
10
11 void rev(int n){
12     for(int i=0;i<c;i++){
13         maze[n][i]=maze[n][i]^1;
14     }
15 }
16
17 int cal(){
18     int sum=0;
19     for(int j=0;j<c;j++){
20         int cou1=0;
21         for(int i=0;i<r;i++){
22             cou1+=maze[i][j]; //统计1的个数
23         }
24         sum+=max(cou1,r-cou1);
25     }
26     return sum;
27 }
28
29 void dfs(int n){
30     if(n==r){
31         maxRes=max(maxRes,cal());
32         return;
33     }
34     rev(n);
35     dfs(n+1);
36     rev(n);
37     dfs(n+1);
38 }
39
40 void solve(){
41     scanf("%d%d",&r,&c);
42     while(r!=0||c!=0){
43         maxRes=0;
44         for(int i=0;i<r;i++){
45             for(int j=0;j<c;j++){
46                 scanf("%d",&maze[i][j]);
47             }
48         }
49         dfs(0);
50         printf("%d\n",maxRes);
51         scanf("%d%d",&r,&c);
52     }
53 }
54
55 int main(){
56     solve();
57     return 0;
58 }