UVa 10400

　　题目大意：给出n(n<100)个正整数和一个目标数，按照给出数的顺序，运用+、-、*、/四则运算（不考虑优先级），判断能否得出所要的结果。

　　首先考虑的就是暴力枚举，不过时间复杂度为O(4ⁿ)，会超时。由于题目限定中间运算结果在[-32000, 32000]内，当n到一定程度后（4ⁿ远远大于64000后），就会存在大量的重复子问题，可以通过记忆化搜索的方法去重，具体到这个问题就是vis数组的运用。

 1 #include <cstdio>
 2 #include <cstring>
 3 #define MAXN 100+10
 4 
 5 long long a[MAXN], target;
 6 char op[MAXN];
 7 int n;
 8 bool ok, vis[MAXN][32000*2+100];
 9 
10 bool judge(int cur, int n)
11 {
12     return n >= -32000 && n <= 32000 && !vis[cur][n+32000];
13 }
14 
15 void dfs(int cur, long long res)
16 {
17     if (cur == n )
18     {
19         if (res == target)  ok = true;
20         return;
21     }
22     if (!ok && judge(cur, res+a[cur]))
23     {
24         op[cur] = '+';
25         vis[cur][res+a[cur]+32000] = true;
26         dfs(cur+1, res+a[cur]);
27     }
28     if (!ok && judge(cur, res-a[cur]))
29     {
30         op[cur] = '-';
31         vis[cur][res-a[cur]+32000] = true;
32         dfs(cur+1, res-a[cur]);
33     }
34     if (!ok && judge(cur, res*a[cur]))
35     {
36         op[cur] = '*';
37         vis[cur][res*a[cur]+32000] = true;
38         dfs(cur+1, res*a[cur]);
39     }
40     if (!ok && res % a[cur] == 0 && judge(cur, res/a[cur]))
41     {
42         op[cur] = '/';
43         vis[cur][res/a[cur]+32000] = true;
44         dfs(cur+1, res/a[cur]);
45     }
46 }
47 
48 int main()
49 {
50 #ifdef LOCAL
51     freopen("in", "r", stdin);
52 #endif
53     int T;
54     scanf("%d", &T);
55     while (T--)
56     {
57         scanf("%d", &n);
58         for (int i = 0; i < n; i++)
59             scanf("%lld", &a[i]);
60         scanf("%lld", &target);    
61         ok = false;
62         memset(vis, 0, sizeof(vis));
63         vis[0][a[0]+32000] = true;
64         dfs(1, a[0]);
65         if (ok)
66         {
67             for (int i = 0; i < n-1; i++)
68                 printf("%lld%c", a[i], op[i+1]);
69             printf("%lld=%lld
", a[n-1], target);
70         }
71         else  printf("NO EXPRESSION
");
72     }
73     return 0;
74 }

View Code

　　也可以用递推的方法求解，不过在打印结果的时候要麻烦一些，二者的思想是一样的。