AOJ 0525 穷举 - 7hat - 博客园

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0525
题意：有一个烤饼器可以烤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函数。对于每一行都确定动作时，统计每一列翻时会出现的正面朝上的值以及不翻时的值，取较大数。此时为行动作确定时，列动作可以做到的最优值。因此穷举所有行情况即可求出实际最优值。
http://www.hankcs.com/program/cpp/aoj-0525-osenbei-challenge-programming-contest-2nd-edition-exercises-answers.html
枚举的话，先从行开始，一共有2^R种翻转可能，行翻转完毕再翻转列。列的翻转不必真的flip，只需要统计一下朝上的煎饼果子和朝下的煎饼果子，两者比较取其最大值即可。

bitset<10000> cookie[10];

int main(int argc, char *argv[])

{

    int R, C;

    while(cin >> R >> C && R > 0)

    {

        int i, j;

        for (i = 0; i < R; ++i)

        {

            for (j = 0; j < C; ++j)

            {

                bool upwards;

                cin >> upwards;

                cookie[i][j] = upwards;

            }

        }

        // 在横向一共有2^R种变换

        int permute_r = 1 << R;

        int result = 0;

        for (i = 0; i < permute_r ; ++i)

        {

            // 完成当前的变换

            for (j = 0; j < R; ++j)

            {

                // 这一行是否应当翻个面

                if (i & (1 << j))

                {

                    cookie[j].flip();

                }

            }

            // 对每一列分别算出朝上和朝下的煎饼个数，取其最大值

            int possible_answer = 0;

            for (j = 0; j < C; ++j)

            {

                int up_cookie_count = 0;

                for (int k = 0; k < R; ++k)

                {

                    if (cookie[k][j])

                    {

                        ++up_cookie_count;

                    }

                }

                possible_answer += max(up_cookie_count, R - up_cookie_count);

            }

            // 结果取最大值

            result = max(result, possible_answer);

             

            // 复原

            for (j = 0; j < R; ++j)

            {

                if (i & (1 << j))

                {

                    cookie[j].flip();

                }

            }

        }

        cout << result << endl;

    }

    return 0;

}

http://www.cnblogs.com/7hat/p/3605315.html

int R, C;
12 bitset<MAX_C> a[MAX_R];
14 int ans;
16 void dfs(int k){
17     if(k == R){
18         //row certain
19         int result = 0;            //cur max value
20         for(int j = 0; j < C; j ++){
21             int upNum = 0;            //up numbers without fliping
22             for(int i = 0; i < R; i ++){
23                 if(a[i][j]) upNum ++;
24             }
25             result += max(upNum, R - upNum);    
26         }
27         ans = max(ans, result);
28         return;
29     }
30     //without fliping
31     dfs(k + 1);
32     //·flip
33     a[k].flip();
34     dfs(k + 1);
36     a[k].flip();
37 }
39 void solve(){
40     ans = 0;
41     dfs(0);
42     printf("%d\n", ans);
43 }
45 int main(int argc, char const *argv[]){
46 
47     while(scanf("%d %d", &R, &C)){
48         if(R == 0 && C == 0) break;
49 
50         for(int i = 0; i < R; i ++){
51             for(int j = 0; j < C; j ++){
52                 bool tmp;
53                 scanf("%d", &tmp);
54                 a[i][j] = tmp;
55             }
56         }
57         solve();
58     }
60     return 0;
61 }

Read full article from AOJ 0525 穷举 - 7hat - 博客园