AIZU-0033 Ball
Q:有一个形似央视大楼（Orz）的筒，从A口可以放球，放进去的球可通过挡板DE使其掉进B裤管或C裤管里，现有带1-10标号的球按给定顺序从A口放入，问是否有一种控制挡板的策略可以使B裤管和C裤管中的球从下往上标号递增。
输入：第一行输入数据组数N。接下来N行为N组具体数据，每组数据中有10个整数，代表球的放入顺序。
输出：对于每组数据，若策略存在，输出YES；若不存在，输出NO
#include <iostream>
#include <stdlib.h>
using namespace std;
void DFS(int* arr, int pos, int* res, int index, bool& flag) {
if (pos >= 10||flag) //数组出界或者找到满足条件时返回
{
return;
}
if ((index==0) || (index >= 1 && res[index - 1] < arr[pos])) //将A数组中的最后一个元素与源数组的pos元素比较
{ //如果小于，则加入A数组，否则加入B数组
res[index] = arr[pos];
arr[pos] = 0;
}
DFS(arr, pos+1, res, index+1, flag); //递归查找后面的元素
if (flag)
{
return;
}
int pre = 0; //A数组肯定是有序的，判断B数组是否有序？
int cur = 0; //就可以得到是否满足条件
flag = true;
for (int i = 0; i < 10; i++)
{
if (arr[i]!=0)
{
pre = pre == 0 ? arr[i] : cur;
cur = arr[i];
if (cur < pre)
{
flag = false;
break;
}
}
}
}
int main()
{
int N, arr[11], res[10];
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < 10; j++)
{
cin >> arr[j];
}
bool flag = false;
DFS(arr, 0, res, 0, flag);
if (flag)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
system("pause");
return 0;
}
