AOJ 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函数。对于每一行都确定动作时，统计每一列翻时会出现的正面朝上的值以及不翻时的值，取较大数。此时为行动作确定时，列动作可以做到的最优值。因此穷举所有行情况即可求出实际最优值。

 #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 ;

 }

巴特西

AOJ 0525 穷举

最新文章

热门文章