AOJ 0525 Osenbei【穷竭搜索】

AOJ 0525

题意：

有一个烤饼器可以烤r行c列的煎饼，煎饼可以正面朝上（用1表示）也可以背面朝上（用0表示）。一次可将同一行或同一列的煎饼全部翻转。现在需要把尽可能多的煎饼翻成正面朝上，问最多能使多少煎饼正面朝上？

输入：多组输入，每组第一行为二整数r, c (1 ≤ r ≤ 10, 1 ≤ c ≤ 10 000)，剩下r行c列表示煎饼初始状态。r=c=0输入结束

输出：对于每组输入，输出最多能使多少煎饼正面朝上

这个是二维的穷举，因为列数比较多行数比较少，所以可对行做dfs穷举所有行的情况。这里用bitset保存每一行的情况，对于行的翻转，只需要用自带的flip函数。对于每一行都确定动作时，统计每一列翻时会出现的正面朝上的值以及不翻时的值，取较大数。此时，行动作确定时，列动作可以做到的最优值。因此穷举所有行情况即可求出实际最优值。

#include<iostream>#include<algorithm>#include<string.h>#include<cstring>#include<vector>#include<set>#include<stack>#include<bitset>using namespace std;const int MAX_R=10;const int MAX_C=10000;int R,C,ans;bitset<MAX_C> a[MAX_R];void dfs(int k){if(k==R){int result=0;for(int i=0;i<C;i++){int sum=0;for(int j=0;j<R;j++){if(a[j][i])sum++;}result+=max(sum,R-sum);}ans=max(ans,result);return;}dfs(k+1);//without flippinga[k].flip();dfs(k+1);//with flipping}int main(){while(cin>>R>>C&&R&&C){for(int i=0;i<R;i++)for(int j=0;j<C;j++){bool tmp;cin>>tmp;a[i][j]=tmp;}ans=0;dfs(0);cout<<ans<<endl;}return 0;}

如果觉得《AOJ 0525 Osenbei【穷竭搜索】》对你有帮助，请点赞、收藏，并留下你的观点哦！