uva 10400 - Game Show Math

題目意思：     給定n個數和一個目標數，問我們能否找到一個表達式使得這n個數算出來最後的結果等於這個目標值，注意這裡的所有運算的優先級一樣，都是從左向右的。

解題思路：     1：思路：DFS+狀態判重
                       2：由於這一題的時間給了20s，那麼DFS是沒問題的。我們只要從第一個開始進行DFS，然後每一次當前是否滿足一下條件：1 當前和-32000<=sum<=32000    2當前的狀態vis[i][sum]沒有出現過   （當使用“/”時候還有判斷 是否當前sum%num[i] =0，這裡的除號比較不一樣）
                       3：這種題目一般用搜索來做，但是要注意狀態的判重，像這一題由於到達num[i]的時候可能求出來的sum不同，所以開個二維vis數組來保存當前狀態。路徑保存用path數組來記錄

代碼：
[cpp] 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <set> 
using namespace std; 
#define MAXN 110 
http:// 
int t, p, target, flag; 
int num[MAXN], path[MAXN], ans[MAXN]; 
int vis[MAXN][100000]; 
 
int judge(int m , int pos){ 
    if(m >= -32000 && m <= 32000 && !vis[pos][m]) 
        return 1; 
    return 0; 
} 
 
void DFS(int sum, int pos) { 
    if (pos >= p) { 
        if (sum == target && !flag) {//保存一次即可 
            memcpy(ans, path, sizeof (ans)); 
            flag = 1; 
        } 
        return; 
    } 
    //四種運算 
    if (!flag) {//‘+’ 
        if(judge(sum+num[pos] , pos)){ 
            vis[pos][sum+num[pos]] = 1; 
            path[pos-1] = 1 ; 
            DFS(sum+num[pos] , pos+1); 
        } 
    } 
    if (!flag) {//‘-’ 
        if(judge(sum-num[pos] , pos)){ 
            vis[pos][sum-num[pos]] = 1; 
            path[pos-1] = 2 ; 
            DFS(sum - num[pos], pos + 1); 
        } 
    } 
    if (!flag) {//‘*’ 
        if(judge(sum*num[pos] , pos)){ 
            vis[pos][sum*num[pos]] = 1; 
            path[pos-1] = 3 ; 
            DFS(sum*num[pos] , pos+1); 
        } 
    } 
    if (sum % num[pos] == 0 && !flag){//‘/’ 
        if(judge(sum/num[pos] , pos)){ 
            vis[pos][sum/num[pos]] = 1; 
            path[pos-1] = 4 ; 
            DFS(sum / num[pos] , pos+1); 
        } 
    } 
} 
 
void output() { 
    for (int i = 0; i < p; i++) { 
        printf("%d", num[i]); 
        if (ans[i] == 1) printf("+"); 
        if (ans[i] == 2) printf("-"); 
        if (ans[i] == 3) printf("*"); 
        if (ans[i] == 4) printf("/"); 
    } 
    printf("=%d\n", target); 
} 
 www.2cto.com
int main() { 
    //freopen("input.txt" , "r" , stdin); 
    scanf("%d%*c", &t); 
    while (t--) { 
        scanf("%d", &p); 
        for (int i = 0; i < p; i++) 
            scanf("%d", &num[i]); 
        scanf("%d", &target); 
        memset(path, 0, sizeof (path)); 
        memset(vis, 0, sizeof(vis)); 
        flag = 0 ; vis[0][num[0]] = 1; 
        DFS(num[0], 1); 
        if (flag) output(); 
        else printf("NO EXPRESSION\n"); 
    } 
    return 0; 
}