题目链接

Ball Aizu - 0033

思路

可以递归求也可以非递归求，笔者用递归实现。

非递归的方法就是用二进制表示，0给b，1给c，分完组后再验证。

时间复杂度

$$ 每组O(2^N) $$

代码

#include <cstdio>
#include <stack>
using namespace std;

const int MAXN = 15;
int a[MAXN];

stack<int> b, c;
bool f = false;

void dfs(int x) {
    if (f) {
        return;
    }

    if (x == 11) {
        f = true;
        return;
    }

    if (b.size() == 0 || b.top() < a[x]) {
        b.push(a[x]);
        dfs(x + 1);
        b.pop();
    }

    if (c.size() == 0 || c.top() < a[x]) {
        c.push(a[x]);
        dfs(x + 1);
        c.pop();
    }
}

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    while (T--) {
        for (int i = 1; i <= 10; i++) {
            scanf("%d", &a[i]);// don't forget &
        }
        f = false;
        dfs(1);
        printf("%s\n", f ? "YES" : "NO");
    }
    return 0;
}