放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

POJ 3185 The Water Bowls 题解 《挑战程序设计竞赛》

目录

POJ 3185 The Water Bowls

翻盖有奖:将一列碗翻成口朝上,一把下去可能同时反转3个或2个(首尾),求最小翻转次数。

3.2常用技巧精选(一)

反转

似乎穷举也能过,不过太蠢了。反转法只需枚举2次,分别是从第一个开始翻和从第二个开始翻。反转法跟尺取法其实有点像,都是限定一个区间,往前挪动,尾部挪动之后,需要减掉尾部的影响。

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_BOW 20 + 1	// 逻辑上多1个,多的这个讨论
int dir[MAX_BOW];	// 方向:1下0上
int f[MAX_BOW];		// 区间[i, i + K -1]是否进行翻转

// 固定K=3,求最少翻转次数,first表示第0个的方向
// INT_MAX表示不可能
int calc(const int& first)
{
	const int N = MAX_BOW;
	memset(f, 0, sizeof(f));
	dir[0] = first;
	int res = 0;
	int sum = 0; // f的和
	for (int i = 0; i < N - 1; ++i)
	{
		// 计算区间[i, i + K -1]
		if ((dir[i] + sum) & 1)
		{
			// 翻转
			++res;
			f[i] = 1;
		}
		sum += f[i];
		if (i - 2 >= 0)
		{
			sum -= f[i - 2];
		}
	}

	// 检查剩下的
	if ((dir[N - 1] + sum) & 1)
	{
		return INT_MAX;
	}

	return res;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	for (int i = 1; i < MAX_BOW; ++i)
	{
		cin >> dir[i];
	}
	cout << min(calc(0), calc(1)) << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
12883342 hankcs 3185 Accepted 244K 32MS C++ 1126B 2014-05-16 14:17:47

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 3185 The Water Bowls 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

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