首页 > 代码库 > AOJ-0525 Osenbei-翻煎饼(穷竭搜索,BFS,BITSET)
AOJ-0525 Osenbei-翻煎饼(穷竭搜索,BFS,BITSET)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0525
题意:药药!切克闹! 煎饼果子来一套!有一个烤饼器可以烤r行c列的煎饼,煎饼可以正面朝上(用1表示)也可以背面朝上(用0表示)。一次可将同一行或同一列的煎饼全部翻转。现在需要把尽可能多的煎饼翻成正面朝上,问最多能使多少煎饼正面朝上?
输入:多组输入,每组第一行为二整数r, c (1 ≤ r ≤ 10, 1 ≤ c ≤ 10 000),剩下r行c列表示煎饼初始状态。r=c=0表示输入结束。
输出:对于每组输入,输出最多能使多少煎饼正面朝上
注意数据范围!!从这里联想到解题方法,顺带查阅bitset的相关资料!(笔者前几篇博客有)
最近做的题感觉bfs什么时候都能够插一脚哈!!
.
.
.
.
.
.
.
.
.
.
分析:这个是二维的穷举,因为列数比较多行数比较少,所以可对行做深度优先遍历穷举所有行的情况。这里用bitset保存每一行的情况,对于行的翻装,只需要用自带的flip函数。对于每一行都确定动作时,统计每一列翻时会出现的正面朝上的值以及不翻时的值,取较大数。此时为行动作确定时,列动作可以做到的最优值。因此穷举所有行情况即可求出实际最优值。
#include <cstdio> #include <algorithm> #include <bitset> using namespace std; const int MAX_R = 10; const int MAX_C = 10000; //input int R, C; bitset<MAX_C> a[MAX_R]; int ans; void dfs(int k){ if(k == R){ //row certain int result = 0; //cur max value for(int j = 0; j < C; j ++){ int upNum = 0; //up numbers without fliping for(int i = 0; i < R; i ++){ if(a[i][j]) upNum ++; } result += max(upNum, R - upNum); } ans = max(ans, result); return; } //without fliping dfs(k + 1); //·flip a[k].flip(); dfs(k + 1); } void solve(){ ans = 0; dfs(0); printf("%d\n", ans); } int main(int argc, char const *argv[]){ while(scanf("%d %d", &R, &C)){ if(R == 0 && C == 0) break; for(int i = 0; i < R; i ++){ for(int j = 0; j < C; j ++){ bool tmp; scanf("%d", &tmp); a[i][j] = tmp; } } solve(); } return 0; }
AOJ-0525 Osenbei-翻煎饼(穷竭搜索,BFS,BITSET)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。