AOJ 0033 Ball《挑战程序设计竞赛(第2版)》练习题答案 � 码农场

2.1 最基础的"穷竭搜索" 深度优先搜索

AOJ 0033 Ball

有一个形似央视大楼（Orz）的筒，从A口可以放球，放进去的球可通过挡板DE使其掉进B裤管或C裤管里，现有带1-10标号的球按给定顺序从A口放入，问是否有一种控制挡板的策略可以使B裤管和C裤管中的球从下往上标号递增。

输入：
第一行输入数据组数N。接下来N行为N组具体数据，每组数据中有10个整数，代表球的放入顺序。
输出：
对于每组数据，若策略存在，输出YES；若不存在，输出NO

Sample Input

2
3 1 4 2 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

http://blog.csdn.net/synapse7/article/details/14454885
用二进制枚举即可。




int main(int argc, char *argv[])

{

    int n;

    cin >> n;

    while (n--)

    {

        int ball[10];

         

        for (int i = 0; i < 10; ++i)

        {

            cin >> ball[i];

        }

        bitset<10> direction;

        int all = 1024;

        while (all-- > 0)

        {

            direction = static_cast<bitset<10> >(all);

            bool perfect = true;

            int left = 0;

            int right = 0;

            for (int i = 0; i < 10; ++i)

            {

                if (direction[i])

                {

                    if (ball[i] > left)

                    {

                        left = ball[i];

                    }

                    else

                    {

                        perfect = false;

                        break;

                    }

                }

                else

                {

                    if (ball[i] > right)

                    {

                        right = ball[i];

                    }

                    else

                    {

                        perfect = false;

                        break;

                    }

                }

            }

            if (perfect)

            {

                break;

            }

        }

     

        if (all >= 0)

        {

            cout << "YES" << endl;

        }

        else

        {

            cout << "NO" << endl;

        }

    }

    return 0;

}

http://www.cnblogs.com/7hat/p/3590540.html

int a[10];

bool dfs(int k, int B, int C){
    if(k == 10) return true;
    if(a[k] > B){
        if(dfs(k + 1, a[k], C))
            return true;
    }
    if(a[k] > C){
        if(dfs(k + 1, B, a[k]))
            return true;
    }
    return false;
}

void solve(){
    if(dfs(0, 0, 0))
        printf("YES\n");
    else
        printf("NO\n");
}

int main(int argc, char const *argv[]){

    int t;
    scanf("%d", &t);
    while(t --){
        for(int i = 0; i < 10; i ++)
            scanf("%d", &a[i]);
        solve();
    }

    return 0;
}

Read full article from AOJ 0033 Ball《挑战程序设计竞赛(第2版)》练习题答案 � 码农场