放牧代码和思想
专注自然语言处理、机器学习算法

AOJ 0525 Osenbei《挑战程序设计竞赛(第2版)》练习题答案

2.1 最基础的“穷竭搜索” 穷竭搜索

AOJ 0525  Osenbei

题意:药药!切克闹! 煎饼果子来一套!有一个烤饼器可以烤r行c列的煎饼,煎饼可以正面朝上(用1表示)也可以背面朝上(用0表示)。一次可将同一行或同一列的煎饼全部翻转。现在需要把尽可能多的煎饼翻成正面朝上,问最多能使多少煎饼正面朝上? 
         输入:多组输入,每组第一行为二整数r, c (1 ≤ r ≤ 10, 1 ≤ c ≤ 10 000),剩下r行c列表示煎饼初始状态。r=c=0表示输入结束。 
         输出:对于每组输入,输出最多能使多少煎饼正面朝上。 

中文参考http://bbs.byr.cn/#!article/ACM_ICPC/73337?au=Milrivel 

又是枚举,作为2.1节最后一题,中规中矩。我看到这题的第一眼就觉得,这题简直是为了推广bitset而设的宣传!由于煎饼的行数远远小于列数,所以只需要10个bitset就可以表示整个煎饼器。对于煎饼的翻转,可以利用bitset::flip来实现,连英文flip都对上了!

枚举的话,先从行开始,一共有2^R种翻转可能,行翻转完毕再翻转列。列的翻转不必真的flip,只需要统计一下朝上的煎饼果子和朝下的煎饼果子,两者比较取其最大值即可。

#include <iostream>
#include <bitset>
#include <algorithm>

using namespace std;

bitset<10000> cookie[10];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{

    int R, C;
	while(cin >> R >> C && R > 0)
	{
		int i, j;
		for (i = 0; i < R; ++i)
		{
			for (j = 0; j < C; ++j)
			{
				bool upwards;
				cin >> upwards;
				cookie[i][j] = upwards;
			}
		}

		// 在横向一共有2^R种变换
		int permute_r = 1 << R;
		int result = 0;
		for (i = 0; i < permute_r ; ++i)
		{
			// 完成当前的变换
			for (j = 0; j < R; ++j)
			{
				// 这一行是否应当翻个面
				if (i & (1 << j))
				{
					cookie[j].flip();
				}
			}
			

			// 对每一列分别算出朝上和朝下的煎饼个数,取其最大值
			int possible_answer = 0;
			for (j = 0; j < C; ++j)
			{
				int up_cookie_count = 0;
				for (int k = 0; k < R; ++k)
				{
					if (cookie[k][j])
					{
						++up_cookie_count;
					}
				}
				possible_answer += max(up_cookie_count, R - up_cookie_count);
			}
			// 结果取最大值
			result = max(result, possible_answer);
			
			// 复原
			for (j = 0; j < R; ++j)
			{
				if (i & (1 << j))
				{
					cookie[j].flip();
				}
			}
		}
		cout << result << endl;
	}

    return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » AOJ 0525 Osenbei《挑战程序设计竞赛(第2版)》练习题答案

分享到:更多 ()

评论 3

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    博主好厉害 ,这段代码太妙了
    int permute_r = 1 << R;
    int result = 0;
    for (i = 0; i < permute_r ; ++i)
    {
    // 完成当前的变换
    for (j = 0; j < R; ++j)
    {
    // 这一行是否应当翻个面
    if (i & (1 << j))
    {
    cookie .flip();
    }
    }

    理解了半天才明白,这样可以在两个循环里面就枚举2^N种情况,不然要我自己想的话,可能要N个循环……每个里面决定是否翻转第N个。

    清和9个月前 (02-03)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机