UVA 10344 23 out of 5(搜索+全排列)

題意：有5個數和+ - * 三種運算，問5個數經過各種運算能否得到23.

思路：簡單的搜索吧，用next_permutation 求出各種排列 再搜索一遍。

//0 KB	719 ms
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int a[5];
bool flag;

void DFS(int pre,int cur)
{
    if (flag) return ;
    if (cur == 5&&pre == 23)
    {
        flag = true;
        return ;
    }
    if (cur > 4)
        return ;
    for (int i = 0;i < 3;i ++)
    {
        if (i == 0)
            DFS(pre+a[cur],cur+1);
        if (i == 1)
            DFS(pre-a[cur],cur+1);
        if (i == 2)
            DFS(pre*a[cur],cur+1);
    }

}
int main ()
{
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif
    int i,cnt;
    while (1)
    {
        cnt = 0;
        for (i = 0;i < 5;i ++)
        {
            scanf ("%d",&a[i]);
            if (!a[i])
                cnt ++;
        }
        if (cnt == 5) break;
        sort(a,a+5);
        flag = false;
        do
        {
            DFS(a[0],1);
        }while (next_permutation(a,a+5)&&!flag);

        if (flag) printf ("Possible\n");
        else printf ("Impossible\n");
    }
    return 0;
}