【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