题目链接：uva 817 - According to Bartjens
题目大意：给出一个数字，在中间可以任意插入+，-，*使得其变成一个式子（乘号先计算），要求输出式子计算结果为2000的所有情况，按照字典序输出。注意必须要添加计算符，2000=是不可以的。
解题思路：因为n不会超过9，所以暴力枚举每个数字后面的字符，复杂度4^8。然后计算表达式的值是否为2000.
注意不要出现00，01这样的数字。
#include#include #include #include #include #include using namespace std; const char sign[4] = { '*', '+', '-' }; const int N = 20; int n, c[N]; bool flag; char str[N]; set s; void init() { s.clear(); n = strlen(str) - 2; flag = true; } bool judge(char* t) { int len = strlen(t); int num[N], cNum = 0, cOp = 0; char op[N]; int sum = 0; bool bo = false, ok = false; for (int i = 0; i <= len; i++) { if (t[i] >= '0' && t[i] <= '9') { sum = sum * 10 + t[i] - '0'; if (bo) return false; if (sum == 0) bo = true; } else if(ok) { int u = num[--cNum]; num[cNum++] = sum * u; sum = 0; bo = false; if (t[i] != '*' && t[i] != '\0') { op[cOp++] = t[i]; ok = false; } } else if (t[i] == '*') { num[cNum++] = sum; sum = 0; ok = true; bo = false; } else { num[cNum++] = sum; sum = 0; if (t[i] != '\0') op[cOp++] = t[i]; bo = false; } } sum = num[0]; for (int i = 1; i < cNum; i++) { if (op[i - 1] == '-') sum -= num[i]; else sum += num[i]; } if (sum == 2000) return true; return false; } void handle() { char f[N]; int t = 0; for (int i = 0; i <= n; i++) { f[t++] = str[i]; if(i != n && c[i] != 3) f[t++] = sign[c[i]]; } f[t] = '\0'; if (judge(f)) { string g = f; s.insert(g); flag = false; } } void dfs(int d) { if (d >= n) { handle(); return; } for (c[d] = 0; c[d] < 4; c[d]++) dfs(d + 1); } void solve() { if (strcmp(str, "2000=") == 0) { printf(" IMPOSSIBLE\n"); return; } dfs(0); if (flag) printf(" IMPOSSIBLE\n"); else { for (set ::iterator i = s.begin(); i != s.end(); i++) cout << " " << *i << "=" << endl; } } int main () { int cas = 1; while (scanf("%s", str) == 1 && strcmp(str, "=") ) { printf("Problem %d\n", cas++); init(); solve(); } return 0; }