中小学门户网站建设,网站建设合作品牌,线上商城推广,龙华民治网站建设AOJ 0525 题意#xff1a; 有一个烤饼器可以烤r行c列的煎饼#xff0c;煎饼可以正面朝上#xff08;用1表示#xff09;也可以背面朝上#xff08;用0表示#xff09;。一次可将同一行或同一列的煎饼全部翻转。现在需要把尽可能多的煎饼翻成正面朝上#xff0c;问最多能…AOJ 0525 题意 有一个烤饼器可以烤r行c列的煎饼煎饼可以正面朝上用1表示也可以背面朝上用0表示。一次可将同一行或同一列的煎饼全部翻转。现在需要把尽可能多的煎饼翻成正面朝上问最多能使多少煎饼正面朝上 输入多组输入每组第一行为二整数r, c (1 ≤ r ≤ 10, 1 ≤ c ≤ 10 000)剩下r行c列表示煎饼初始状态。rc0输入结束 输出对于每组输入输出最多能使多少煎饼正面朝上 这个是二维的穷举因为列数比较多行数比较少所以可对行做dfs穷举所有行的情况。这里用bitset保存每一行的情况对于行的翻转只需要用自带的flip函数。对于每一行都确定动作时统计每一列翻时会出现的正面朝上的值以及不翻时的值取较大数。此时行动作确定时列动作可以做到的最优值。因此穷举所有行情况即可求出实际最优值。 #includeiostream
#includealgorithm
#includestring.h
#includecstring
#includevector
#includeset
#includestack
#includebitset
using namespace std;const int MAX_R10;
const int MAX_C10000;int R,C,ans;
bitsetMAX_C a[MAX_R];void dfs(int k)
{if(kR){int result0;for(int i0;iC;i){int sum0;for(int j0;jR;j){if(a[j][i])sum;}resultmax(sum,R-sum);}ansmax(ans,result);return;}dfs(k1);//without flippinga[k].flip();dfs(k1);//with flipping
}int main()
{while(cinRCRC){for(int i0;iR;i)for(int j0;jC;j){bool tmp;cintmp;a[i][j]tmp;}ans0;dfs(0);coutansendl;}return 0;
}转载于:https://www.cnblogs.com/demian/p/6555258.html
