You are given a simple arithmetic expression which consists of only addition and subtraction operators. For example:

1 - 2 + 3 - 4 - 5

You are free to put any parentheses to the expression anywhere you want and as many as you want. However it should be a valid expression after you put the parentheses. The question is how many different numbers can you make? For example, adding parentheses to the above expression can give you 6 different values:

1 - 2 + 3 - 4 - 5     =  -7
1 - (2 + 3 - 4 - 5)   =   5
1 - (2 + 3) - 4 - 5   = -13
1 - 2 + 3 - (4 - 5)   =   3
1 - (2 + 3 - 4) - 5}  =  -5
1 - (2 + 3) - (4 - 5) =  -3

Input 

There will be many expressions in the input. Each expression is written in one line. The expression consists of only N (2N30) non-negative number less than 100, separated by addition or subtraction operators. There will be no operator before the first number.

Output 

For each expression, print the number of different values that can be derived from the expression by adding any number of parentheses.

Sample Input 

1 - 2 + 3 - 4 - 5 
38 + 29 - 91 
54 - 18 + 22 + 74

Sample Output 

6 
1 
3

// TLE
#include <stdio.h>
#include <string.h>
#include <set>
#include <iostream>
using namespace std;
int main() {
    char cmd[1005];
    int i, j, k;
    /*freopen("in.txt", "r+t", stdin);
	freopen("out.txt", "w+t", stdout);*/
    while(gets(cmd)) {
        int len = strlen(cmd);
        int op[105], num[105], nidx = 0, oidx = 0;
        for(i = 0; i < len; ) {
            while(cmd[i] == ' ')
                i++;
            if(cmd[i] >= '0' && cmd[i] <= '9') {
                int tmp = 0;
                while(cmd[i] >= '0' && cmd[i] <= '9')
                    tmp = tmp*10 + cmd[i]-'0', i++;
                num[nidx++] = tmp;
            } else if(cmd[i] == '+' || cmd[i] == '-'){
                op[oidx++] = cmd[i++];
            }
        }
        set<int> dp[50][50];
        for(i = 0; i < nidx; i++) {
            for(j = 0; i+j < nidx; j++) {
                if(i == 0) {
                    dp[j][j+i].insert(num[j]);
                    continue;
                }
                for(k = j; k < i+j; k++) {
                    for(set<int>::iterator it = dp[j][k].begin();
                        it != dp[j][k].end(); it++)
                    for(set<int>::iterator jt = dp[k+1][i+j].begin();
                        jt != dp[k+1][i+j].end(); jt++) {
                        if(op[k] == '+')
                            dp[j][i+j].insert(*it+*jt);
                        else
                            dp[j][i+j].insert(*it-*jt);
                    }
                }
            }
        }
        printf("%d\n", dp[0][nidx-1].size());
    }
    return 0;
}

以下的代碼是網路上得知的寫法。

思路是這個樣子的，狀態是 dp[目前已經放置第幾個數目][有多少個左括弧][數字] = 有 or 無。

然後轉移狀態有四種

#include <stdio.h>
#include <string.h>
#include <set>
#include <iostream>
using namespace std;
char dp[35][35][6006];
int op[105], num[105], nidx = 0, oidx = 0;
int diff[6006] = {};
void dfs(int idx, int right, int sum, int flip) {
    if(idx == nidx) {
        diff[sum+3000] = 1;
        return;
    }
    if(dp[idx][right][sum+3000])
        return;
    dp[idx][right][sum+3000] = 1;
    // no operator
    dfs(idx+1, right, sum + flip*op[idx]*num[idx], flip);
    if(op[idx] == -1) // add -(number
        dfs(idx+1, right+1, sum + (-flip)*num[idx], -flip);
    if(right >= 1) { // (-##### add )[+|-]
        //no operator
        dfs(idx+1, right-1, sum + (-flip)*op[idx]*num[idx], -flip);
        // add -(number
        if(op[idx] == -1)
            dfs(idx+1, right, sum + flip*num[idx], flip);
    }
}
int main() {
    char cmd[1005];
    int i, j, k;
    /*freopen("in.txt", "r+t", stdin);
	freopen("out.txt", "w+t", stdout);*/
    while(gets(cmd)) {
        int len = strlen(cmd);
        op[0] = 1;
        nidx = 0, oidx = 1;
        for(i = 0; i < len; ) {
            while(cmd[i] == ' ')
                i++;
            if(cmd[i] >= '0' && cmd[i] <= '9') {
                int tmp = 0;
                while(cmd[i] >= '0' && cmd[i] <= '9')
                    tmp = tmp*10 + cmd[i]-'0', i++;
                num[nidx++] = tmp;
            } else if(cmd[i] == '+' || cmd[i] == '-'){
                if(cmd[i] == '+')
                    op[oidx++] = 1;
                else
                    op[oidx++] = -1;
                i++;
            }
        }
        memset(dp, 0, sizeof(dp));
        memset(diff, 0, sizeof(diff));
        dfs(0, 0, 0, 1);
        int ret = 0;
        for(i = 0; i <= 6000; i++)
            ret += diff[i];
        printf("%d\n", ret);
    }
    return 0;
}
/*
34 - 19 - 65 + 90 + 42 - 86 - 22 + 45 + 47 - 48 + 39 - 81 - 93 + 10 - 11 - 16 + 95 - 27 + 18 + 9 - 54 - 85 + 82 - 75
96 - 85 + 6 - 63 - 89 - 78 + 2 - 65 + 2 - 81 - 4 + 19 - 41 - 72 + 95

*/