AOJ 0033 Ball

AOJ 0033 Ball

題意

題目我截圖下來了，我大致解釋下。有編號1到10共10個球，從上方丟下去，入口處可以選擇進入左邊或者右邊，最後10個球全部落下去後如果左右兩側都是從小到大的順序，則輸出YES；否則輸出NO。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxpbWcgYWx0PQ=="這裡寫圖片描述" src="http://www.bkjia.com/uploads/allimg/151216/043R92627-1.jpg" title="\" />

代碼

一開始我先測試了一下自己理解的題意是不是對的：

#include 
#include   

using namespace std;

int main() {
    vector left;
    vector right;
    vector all;

    bool flag = true;

    int n;
    cin >> n;
    if (n == 0) return -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            int temp;
            cin >> temp;
            all.push_back(temp);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            if (left.size() > 0) {
                if (all[10 * i + j] > left[left.size() - 1]) {
                    left.push_back(all[10 * i + j]);
                }
                else {
                    if (right.size() > 0) {
                        if (all[10 * i + j] > right[right.size() - 1])
                            right.push_back(all[10 * i + j]);
                        else
                            flag = false;
                    }
                    else {
                        right.push_back(all[10 * i + j]);
                    }
                }
            }
            else {
                left.push_back(all[10 * i + j]);
            }
        }

        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        flag = true;
    }

    return 0;
}

後來提交代碼居然錯了，什麼鬼！！我用題目中的用例測試是對的啊，還是沒有發現原因在哪……

因為知道題意是要求用DFS，所以改改代碼，思路一樣，再試試：

#include
#include 
using namespace std;

bool flag = true;

void solve(queue left, queue right, queue all) {
    if (all.size() > 0) {
        if (left.size() > 0) {
            if (all.front() > left.back()) {
                left.push(all.front());
                all.pop();
                solve(left, right, all);
            }
            else {
                if (right.size() > 0) {
                    if (all.front() > right.back()) {
                        right.push(all.front());
                        all.pop();
                        solve(left, right, all);
                    }
                    else if(all.size() == 0){

                    }
                    else {
                        flag = false;
                    }
                }
                else {
                    right.push(all.front());
                    all.pop();
                    solve(left, right, all);
                }
            }
        }
        else {
            left.push(all.front());
            all.pop();
            solve(left, right, all);
        }
    }
}

int main() { 
    int n;
    scanf("%d", &n);
    for (; n > 0; n--) {
        queue all;
        queue left;
        queue right;
        for (int i = 0; i < 10; i++) {
            int temp;
            scanf("%d", &temp);
            all.push(temp);
        }
        solve(left, right, all);
        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }   
    return 0;
}

這次終於可以了，證明我的思路沒有問題的呀！

找了份代碼過來，變量挺多的：

#include
#include
#include
using namespace std;

int main() {
    stack b, c;
    int a[10];
    bool which[11];
    int data[11];
    int index;
    int n, m, A;
    int i, j;
    cin >> n;
    for (i = 0; i> m;
            a[j] = m;
            data[j + 1] = 0;
        }
        b.push(0);
        c.push(0);
        while (index >= 0) {
            A = a[index];
            if (b.top() < A && (data[A] != 1 && data[A] != 3)) {
                b.push(A);
                data[A] += 1;
                which[A] = true;
            }
            else if (c.top() < A && (data[A] != 2 && data[A] != 3)) {
                c.push(A);
                data[A] += 2;
                which[A] = false;
            }
            else {
                index--;
                if (index < 0) {
                    break;
                }
                else if (which[a[index]]) {
                    b.pop();
                }
                else {
                    c.pop();
                }
                continue;
            }
            index++;
            if (index > 9) {
                cout << "YES" << endl;
                break;
            }
        }
        if (index < 0) {
            cout << "NO" << endl;
        }
    }
}