本文共 1959 字,大约阅读时间需要 6 分钟。
Osenbei
おせんべい 問題IOI製菓では,創業以来の伝統の製法で煎餅(せんべい)を焼いている.この伝統の製法は,炭火で一定時間表側を焼き,表側が焼けると裏返して,炭火で一定時間裏側を焼くというものである.この伝統を守りつつ,煎餅を機械で焼いている.この機械は縦 R (1 ≤ R ≤ 10) 行, 横 C (1 ≤ C ≤ 10000) 列の長方形状に煎餅を並べて焼く.通常は自動運転で,表側が焼けたら一斉に煎餅を裏返し裏側を焼く.
ある日,煎餅を焼いていると,煎餅を裏返す直前に地震が起こり何枚かの煎餅が裏返ってしまった.幸いなことに炭火の状態は適切なままであったが,これ以上表側を焼くと創業以来の伝統で定められている焼き時間を超えてしまい,煎餅の表側が焼けすぎて商品として出荷できなくなる.そこで,急いで機械をマニュアル操作に変更し,まだ裏返っていない煎餅だけを裏返そうとした.この機械は,横の行を何行か同時に裏返したり縦の列を何列か同時に裏返したりすることはできるが,残念なことに,煎餅を1枚ごと裏返すことはできない.
裏返すのに時間がかかると,地震で裏返らなかった煎餅の表側が焼けすぎて商品として出荷できなくなるので,横の何行かを同時に1回裏返し,引き続き,縦の何列かを同時に1回裏返して,表側を焼きすぎずに両面を焼くことのできる煎餅,つまり,「出荷できる煎餅」の枚数をなるべく多くすることにした.横の行を1行も裏返さない,あるいは,縦の列を1列も裏返さない場合も考えることにする.出荷できる煎餅の枚数の最大値を出力するプログラムを書きなさい.
地震の直後に,煎餅が次の図のような状態になったとする.黒い丸が表側が焼ける状態を,白い丸が裏側が焼ける状態を表している.
1行目を裏返すと次の図のような状態になる.
さらに, 1列目と5列目を裏返すと次の図のような状態になる.この状態では,出荷できる煎餅は9枚である.
ヒントR の上限 10 は C の上限 10000 に比べて小さいことに注意せよ.
入力入力は複数のデータセットからなる.各データセットは以下の形式で与えられる.
入力の1行目には2つの整数 R, C (1 ≤ R ≤ 10, 1 ≤ C ≤ 10 000) が空白を区切りとして書かれている.続く R 行は地震直後の煎餅の状態を表す. (i+1) 行目 (1 ≤ i ≤ R) には, C 個の整数 ai,1, ai,2, ……, ai,C が空白を区切りとして書かれており, ai,j は i 行 j 列 の煎餅の状態を表している. ai,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上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。
题意:每次可以翻转一行或一列,求最多能有多少个0
解题思路:首先看数据的大小,行数最多只有10行,因此可以枚举行,最多2^10,也就是1024种,然后看列,如果1的个数大于0的个数,则翻转。AC代码:#include#include #include #include #include #include #include #include #include #define maxn 10005using namespace std;int main(){ int r,c,sumr[15],a[15][10005],s,maxs; while(scanf("%d%d",&r,&c)==2&&(r!=0||c!=0)) { memset(sumr,0,sizeof(sumr)); for(int i=0;i >j&1) //翻转过 s+=(c-sumr[j]); else //没翻转 s+=sumr[j]; } for(int p=0;p >j&1)) k++; } else { if(i>>j&1) k++; } } if(k<=r/2) s+=(r-k)-k; } maxs=max(maxs,s); } printf("%d\n",maxs); } return 0;}
转载地址:https://blog.csdn.net/qq_44632981/article/details/98233351 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!