【2012.03.3普及组】烤饼干

题目描述

NOIP烤饼干时两面都要烤，而且一次可以烤R(1<=R<=10)行C(1<=C<=10000)列个饼干，当一面烤到规定时间时，机器会把整个翻过来以接着烤另一面。

有一天，正当机器准备翻饼干时发生了地震，有一些饼干被翻了过来，有一些没有。幸运的是，地震过后你可以手工操作，一次可以同时翻若干行或者若干列，但不能单独翻某一个饼干。

写一个程序计算通过翻转使得最终翻过来的饼干的数量得最大值。 例如下图是地震之后的情况，黑点表示未翻转，白点表示已经翻转：

[图片]

翻转第一行后得到:

[图片]

接着翻转第1列和第5列得到下图：

[图片]

这样可以使得9个饼干翻转过来。

题目大意：

给你一个r行c列的01矩阵，每次可以翻转一行或者一列，使其全部反转。假设不限次数，求最多有多少个0。

方法：dp

我们读完题后发现，r最大只有10，所以我们考虑从r下手。我们设f[j]是状态为j的数列中1的个数，那么在经过若干翻转后，在所有序列之间取最小值就行了。
操作方法：二进制状压
在输入之间，对每一行中的每一个进行竖压位，如图所示：

然后，我们用一个循环代表翻转的方法：
For I 0~(1<<n)-1

这代表什么呢？如果不会可以查百度（也可以认为是(2^n)-1 ）

这样就会有所需的变化方式。然后，我们再去枚举每一列，进行与i异或，就等于翻转了。再接着，我们数一数这个序列有多少个1。但是，我们第2重循环的答案不止这个，因为我们没考虑到不变的情况，所以应该是max(1的个数，0的个数)。然后，累加第二重循环的答案，在第一重循环取个最大值，最后输出就行了。
总的来说，一共是有三重循环的，变化方式和列数和数1