AIZU-0033 Ball

Q:有一個(gè)形似央視大樓（Orz）的筒，從A口可以放球，放進(jìn)去的球可通過(guò)擋板DE使其掉進(jìn)B褲管或C褲管里，現(xiàn)有帶1-10標(biāo)號(hào)的球按給定順序從A口放入，問(wèn)是否有一種控制擋板的策略可以使B褲管和C褲管中的球從下往上標(biāo)號(hào)遞增。

輸入：第一行輸入數(shù)據(jù)組數(shù)N。接下來(lái)N行為N組具體數(shù)據(jù)，每組數(shù)據(jù)中有10個(gè)整數(shù)，代表球的放入順序。 
輸出：對(duì)于每組數(shù)據(jù)，若策略存在，輸出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)          //數(shù)組出界或者找到滿足條件時(shí)返回
    {
        return;
    }
    if ((index==0) || (index >= 1 && res[index - 1] < arr[pos]))   //將A數(shù)組中的最后一個(gè)元素與源數(shù)組的pos元素比較
    {                                                              //如果小于，則加入A數(shù)組，否則加入B數(shù)組
        res[index] = arr[pos];
        arr[pos] = 0;
    }
    DFS(arr, pos+1, res, index+1, flag);                          //遞歸查找后面的元素
    if (flag)
    {
        return;
    }
    int pre = 0;                                                  //A數(shù)組肯定是有序的，判斷B數(shù)組是否有序？
    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;
}