UVA_10400

    这个题目可以用dp去解，不妨用f[i][j]表示到第i个数时得到j是否可能，如果可能值为1，否则值为0。由于有负数，所以我们可以把j加32000后再修改对应的f[i][j]的值，这样我们就只要依次递推去看最后f[N-1][target+32000]是否为1即可。

    此外，这个题目要求打印路径，我们在打印路径有两种选择，一种是记录此步的操作，一种是记录上一步的结果。选择记录此步的操作往往比较简便，但由于这个题目可能存在特殊的数据，比如3 1000 0 3 3，如果设计到乘0的操作，我们就没办法通过记录的此步的操作来获取上一步的值了，因此，这个题目还是用记录上一步结果的方式来打印路径更好一些。

#include
     
       #include
      
        #define MAXN 110 #define MAXD 64010 #define D 32000 #define DD 64000 int N, a[MAXN], f[MAXN][MAXD], S, p[MAXN][MAXD]; void printpath(int i, int ans) {
   if(i != 0)     {
   int x = p[i][ans + D] - D; if(x + a[i] == ans)         {
               printpath(i - 1, x);             printf("+");         } else if(x - a[i] == ans)         {
               printpath(i - 1, x);             printf("-");         } else if(a[i] != 0 && x % a[i] == 0 && x / a[i] == ans)         {
               printpath(i - 1, x);             printf("/");         } else         {
               printpath(i - 1, x);             printf("*");         }     }     printf("%d", a[i]); } void solve() {
   int i, j, k, ans; long long int res;     scanf("%d", &N); for(i = 0; i < N; i ++)         scanf("%d", &a[i]);     scanf("%d", &S);     memset(f, 0, sizeof(f));     f[0][a[0] + D] = 1; for(i = 1; i < N; i ++) for(j = 0; j < DD; j ++) if(f[i - 1][j])             {
                   ans = j - D + a[i]; if(ans > -D && ans < D)                 {
                       f[i][ans + D] = 1;                     p[i][ans + D] = j;                 }                 ans = j - D - a[i]; if(ans > -D && ans < D)                 {
                       f[i][ans + D] = 1;                     p[i][ans + D] = j;                 }                 res = (long long int)(j - D) * a[i]; if(res > -D && res < D)                 {
                       f[i][res + D] = 1;                     p[i][res + D] = j;                 } if(a[i] != 0 && (j - D) % a[i] == 0)                 {
                       ans = (j - D) / a[i];                     f[i][ans + D] = 1;                     p[i][ans + D] = j;                 }             } if(!f[N - 1][S + D])         printf("NO EXPRESSION\n"); else     {
           printpath(N - 1, S);         printf("=%d\n", S);     } } int main() {
   int t;     scanf("%d", &t); while(t --)     {
           solve();     } return 0; }