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 flipping
a[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;
}
上一篇:【 D3.js 高级系列 — 8.0 】 标线


下一篇:[解决方案]在Sql Server 2008/2005 数据库还原出现 3154错误