[挑戰程式設計競賽] AOJ 0033 - Ball

題意：

有一個形似央視大樓的筒，從A口可以放球，放進去的球可通過擋闆DE使其掉進B管或C管裡，現有帶1-10标号的球按給定順序從A口放入，問是否有一種控制擋闆的政策可以使B管和C管中的球從下往上标号遞增。  

輸入：

第一行輸入資料組數N。接下來N行為N組具體資料，每組資料中有10個整數，代表球的放入順序。

輸出：

對于每組資料，若政策存在，輸出YES；若不存在，輸出NO。

思路：用二進制枚舉或DFS均可。

DFS：寫法

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <assert.h>
#include <time.h>
typedef long long LL;
const int INF = 500000001;
const double EPS = 1e-9;
const double PI = acos(-1.0);
using namespace std;
int N;
int a[100];
int lleft[100], rright[100];
bool dfs(int deep, int len_left, int len_right)
{
    if(deep != 0 && (len_left >= 2 && (lleft[len_left-1] <= lleft[len_left-2]) || 
       (len_right >= 2 && rright[len_right-1] <= rright[len_right-2])))
    {
        return false;
    }
    if(deep == 10)
    {
        return true;
    }
    if(deep < 10)
    {
        lleft[len_left] = a[deep];
        if(dfs(deep+1, len_left+1, len_right)) return true;
        rright[len_right] = a[deep];
        if(dfs(deep+1, len_left, len_right+1)) return true;
    }
    return false;
}
int main()
{
    //freopen("test0.in", "r", stdin);
    //freopen("test0.out", "w", stdout);
    //srand(time(NULL));
    while(~scanf("%d", &N))
    {
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < 10; j++)
                scanf("%d", &a[j]);
            if(dfs(0, 0, 0))
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
}
           

枚舉二進制寫法：

主要利用10位數的二進制特性：從0000000000 -- 1111111111

當二進制的某位為0表示将小球放在C管裡，否則将目前的小球放在B管裡。

1111111111 轉換為十進制是2^10-1。從0~2^10-1的過程，就枚舉了每個管裡可能的所有組合情況。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <assert.h>
#include <time.h>
typedef long long LL;
const int INF = 500000001;
const double EPS = 1e-9;
const double PI = acos(-1.0);
using namespace std;
int N;
int a[100];
int lleft[100], rright[100], flag;
int main()
{
    //freopen("test0.in", "r", stdin);
    //freopen("test0.out", "w", stdout);
    //srand(time(NULL));
    while(~scanf("%d", &N))
    {
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < 10; j++)
                scanf("%d", &a[j]);
            for(int j = 0; j < 1<<10; ++j)
            {
                int len_left = 0, len_right = 0;
                flag = 1;
                for(int k = 1, cnt = 0; k < 1<<10; k<<=1, cnt++)
                {
                    if(j & k)
                    {
                        lleft[len_left++] = a[cnt];
                    }
                    else
                    {
                        rright[len_right++] = a[cnt];
                    }
                    if((len_left >= 2 && lleft[len_left-1] <= lleft[len_left-2]) || 
                       (len_right >= 2 && rright[len_right-1] <= rright[len_right-2]))
                    {
                        flag = 0;
                        break;
                    }
                }
                if(flag)
                {
                    break;
                }
            }
            if(flag)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
    }
    return 0;
}