aoj 0033 - Ball

問題

問題概要

与えられた数字を2つに分けて、共に、数字が昇順になるようにできるか。

解法

dfsで解いた。dfs(B, C, cnt) := (B:=Bの一番上の数 C:=Cの一番上の数 cnt:=何個目の数字か)を要素として持ち、再帰関数を書けばいい。

ミス

シンプルなdfs

コード

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int a[10];
bool flag = false;

//B:=Bの一番上の数 C:=Cの一番上の数 cnt:=何個目の数字か
void dfs(int B, int C, int cnt){
    if(cnt == 9){
        if(B < a[cnt]) flag = true;
        if(C < a[cnt]) flag = true;
        return;
    }
    if(B < a[cnt]){
        dfs(a[cnt], C, cnt + 1);
    }
    if(C < a[cnt]){
        dfs(B, a[cnt], cnt + 1);
    }
    if(B > a[cnt] && C > a[cnt]){
        return;
    }
}
int main(void){
    int n; cin >> n;
    for (int i = 0; i < n; ++i){
        rep(j, 10) cin >> a[j];
        flag = false;
        dfs(0, 0, 0);
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int a[10];

//B:=Bの一番上の数 C*=Cの一番上の数 cnt:=何個目の数字か
bool dfs(int B, int C, int cnt){
    if(cnt == 10){
        return true;
    }
    if(B < a[cnt]){
        return dfs(a[cnt], C, cnt + 1);
    }
    if(C < a[cnt]){
        return dfs(B, a[cnt], cnt + 1);
    }
    if(B > a[cnt] && C > a[cnt]){
        return false;
    }
}
int main(void){
    int n; cin >> n;
    for (int i = 0; i < n; ++i){
        rep(j, 10) cin >> a[j];
        if(dfs(0, 0, 0)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}