Aizu 0525 Osenbei 搜索 A

Aizu 0525 Osenbei

题目：

IOI製菓では，創業以来の伝統の製法で煎餅（せんべい）を焼いている．この伝統の製法は，炭火で一定時間表側を焼き，表側が焼けると裏返して，炭火で一定時間裏側を焼くというものである．この伝統を守りつつ，煎餅を機械で焼いている．この機械は縦 R (1 ≤ R ≤ 10) 行, 横 C (1 ≤ C ≤ 10000) 列の長方形状に煎餅を並べて焼く．通常は自動運転で，表側が焼けたら一斉に煎餅を裏返し裏側を焼く．

ある日，煎餅を焼いていると，煎餅を裏返す直前に地震が起こり何枚かの煎餅が裏返ってしまった．幸いなことに炭火の状態は適切なままであったが，これ以上表側を焼くと創業以来の伝統で定められている焼き時間を超えてしまい，煎餅の表側が焼けすぎて商品として出荷できなくなる．そこで，急いで機械をマニュアル操作に変更し，まだ裏返っていない煎餅だけを裏返そうとした．この機械は，横の行を何行か同時に裏返したり縦の列を何列か同時に裏返したりすることはできるが，残念なことに，煎餅を１枚ごと裏返すことはできない．

裏返すのに時間がかかると，地震で裏返らなかった煎餅の表側が焼けすぎて商品として出荷できなくなるので，横の何行かを同時に１回裏返し，引き続き，縦の何列かを同時に１回裏返して，表側を焼きすぎずに両面を焼くことのできる煎餅，つまり，「出荷できる煎餅」の枚数をなるべく多くすることにした．横の行を１行も裏返さない，あるいは，縦の列を１列も裏返さない場合も考えることにする．出荷できる煎餅の枚数の最大値を出力するプログラムを書きなさい．

地震の直後に，煎餅が次の図のような状態になったとする．黒い丸が表側が焼ける状態を，白い丸が裏側が焼ける状態を表している．

1行目を裏返すと次の図のような状態になる．

さらに， 1列目と5列目を裏返すと次の図のような状態になる．この状態では，出荷できる煎餅は9枚である．

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

入力の1行目には2つの整数 R, C (1 ≤ R ≤ 10, 1 ≤ C ≤ 10 000) が空白を区切りとして書かれている．続く R 行は地震直後の煎餅の状態を表す． (i+1) 行目 (1 ≤ i ≤ R) には， C 個の整数 a_i,1, a_i,2, ……, a_i,C が空白を区切りとして書かれており， a_i,j は i 行 j 列の煎餅の状態を表している. a_i,j が 1 なら表側が焼けることを， 0 なら裏側が焼けることを表す．

C, R がともに 0 のとき入力の終了を示す.　データセットの数は 5 を超えない．

出力

データセットごとに，出荷できる煎餅の最大枚数を1行に出力する．

入力例

2 5
0 1 0 1 0
1 0 0 0 1
3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1  
0 0

出力例

9
15

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

分析：

装作能看懂日文的样子。。。

然而并不。。。。。

所以先翻译一下

一个r*c的板子，上面有0/1，每次可以翻转一列或者一行，问经过翻转之后怎么使得整体的0最多

看完题整个人都不好了。。。。这TM是什么鬼题啊。。。。

想了很久也没思路

看了网上的题解是因为列数比较少，所以遍历列数，然后再遍历行数来确定每一行最多有多少0

还用了bitset，挺好的一个stl

bitset学习：

https://www.cnblogs.com/RabbitHu/p/bitset.html

然后自己打打打过了

AC代码：

 1 #include <stdio.h>  2 #include <math.h>  3 #include <string.h>  4 #include <algorithm>  5 #include <iostream>  6 #include <string>  7 #include <time.h>  8 #include <queue>  9 #include <string.h> 10 #include <bitset> 11 #define sf scanf 12 #define pf printf 13 #define lf double 14 #define ll long long 15 #define p123 printf("123\n"); 16 #define pn printf("\n"); 17 #define pk printf(" "); 18 #define p(n) printf("%d",n); 19 #define pln(n) printf("%d\n",n); 20 #define s(n) scanf("%d",&n); 21 #define ss(n) scanf("%s",n); 22 #define ps(n) printf("%s",n); 23 #define sld(n) scanf("%lld",&n); 24 #define pld(n) printf("%lld",n); 25 #define slf(n) scanf("%lf",&n); 26 #define plf(n) printf("%lf",n); 27 #define sc(n) scanf("%c",&n); 28 #define pc(n) printf("%c",n); 29 #define gc getchar(); 30 #define re(n,a) memset(n,a,sizeof(n)); 31 #define len(a) strlen(a) 32 #define LL long long 33 #define eps 1e-6 34 using namespace std; 35 int r,c; 36 int sum = 0; 37 int temp = 0; 38 bitset<10500> a[15]; 39 40 int dfs(int x){ 41 if(x == r){ 42 int sum1 = 0; 43 for(int i = 0; i < c; i ++){ 44 int sum0 = 0; 45 for(int j = 0; j < r; j ++){ 46 if(a[j][i])sum0++; 47  } 48 sum1 += max(sum0,r-sum0); 49  } 50 sum = max(sum,sum1); 51 return 0; 52  } 53 dfs(x+1); 54  a[x].flip(); 55 dfs(x+1); 56 } 57 int main() { 58 59 while(~scanf("%d%d",&r,&c) && (r != 0 || c != 0)){ 60 for(int i = 0; i< r; i ++){ 61 for(int j = 0; j < c; j ++){ 62  s(temp); 63 a[i][j] = temp; 64  } 65  } 66 sum = 0; 67 dfs(1); 68  p(sum) pn 69  } 70 return 0; 71 }