码农场
2.1 最基础的“穷竭搜索” 深度优先搜索
有一个形似央视大楼（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版)》练习题答案
#include
using namespace std;
int n;
int a[10];
bool dfs(int i, int left, int right) {
if (i == 9) return a[i] > left || a[i] > right;
if (a[i] > left && dfs(i+1, a[i], right)) return true;
if (a[i] > right && dfs(i+1, left, a[i])) return true;
return false;
}
void solve() {
if (dfs(0,0,0)) cout << "YES" << endl;
else cout << "NO" <> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j > a[j];
}
solve();
}
}