放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

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

2.1 最基础的“穷竭搜索” 深度优先搜索

AOJ 0033 Ball

有一个形似央视大楼(Orz)的筒,从A口可以放球,放进去的球可通过挡板DE使其掉进B裤管或C裤管里,现有带1-10标号的球按给定顺序从A口放入,问是否有一种控制挡板的策略可以使B裤管和C裤管中的球从下往上标号递增。 

输入:

第一行输入数据组数N。接下来N行为N组具体数据,每组数据中有10个整数,代表球的放入顺序。 

输出:

对于每组数据,若策略存在,输出YES;若不存在,输出NO 

翻译来自http://blog.csdn.net/synapse7/article/details/14454885


bitset是我最爱的玩具,通俗易懂,方便好用。

#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;

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

	int n;
	cin >> n;
	while (n--)
	{
		int ball[10];
		
		for (int i = 0; i < 10; ++i)
		{
			cin >> ball[i];
		}

		bitset<10> direction;
		int all = 1024;
		while (all-- > 0)
		{
			direction = static_cast<bitset<10> >(all);
			bool perfect = true;
			int left = 0;
			int right = 0;
			for (int i = 0; i < 10; ++i)
			{
				if (direction[i])
				{
					if (ball[i] > left)
					{
						left = ball[i];
					}
					else
					{
						perfect = false;
						break;
					}
				}
				else
				{
					if (ball[i] > right)
					{
						right = ball[i];
					}
					else
					{
						perfect = false;
						break;
					}
				}
			}
			if (perfect)
			{
				break;
			}
		}
	
		if (all >= 0)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}

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

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

分享到:更多 ()

评论 欢迎留言

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

我的开源项目

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