题目大意：刚开始栈中有一个数字，要求你经过一定的操作后，，栈中最后保留下来的数等于所给的数。
解题思路：纯暴力，但要加上剪枝 1.当前的操作步数中，DUP的次数要大于等于其他操作的和 2.判断的时候，只有操作次数为偶数，且DUP的次数等于其他操作次数的和
;char str[5][10] = {“ADD”,”DIV”,”DUP”,”MUL”,”SUB”};int n, num[maxn], End[maxn];struct opera{int op[15], num, DM;};bool ok(opera t, int Num, int End) {stack<int> s;s.push(Num);s.push(Num);int top1, top2, tmp;for(int i = 1; i < t.num; i++) {if(t.op[i] != 2) {top1 = s.top();s.pop();if(!s.empty()) {top2 = s.top();s.pop();};}switch(t.op[i]) {case 0: tmp = top2 + top1; break;case 4: tmp = top2 – top1; break;case 3: tmp = top2 * top1; break;case 1: if(top1 == 0)return false;tmp = top2 / top1; break;case 2: tmp = s.top();}if(abs(tmp) > 30000)return false;elses.push(tmp);}tmp = s.top();s.pop();if(s.empty() && tmp == End) {return true;};}bool judge(opera t) {for(int i = 0; i < n; i++)if(!ok(t,num[i], End[i]))return false;return true;}bool bfs() {queue<opera> q;opera t;t.op[0] = 2, t.DM = 1, t.num = 1;q.push(t);while(!q.empty()) {opera tmp = q.front(); q.pop();if(tmp.num % 2 == 0 && tmp.DM == tmp.num / 2 && judge(tmp)) {for(int i = 0; i < tmp.num – 1; i++)printf(“%s “,str[tmp.op[i]]);printf(“%s\n”, str[tmp.op[tmp.num – 1]]);return true;}for(int i = 0; i < 5; i++) {opera now = tmp;if(i == 2)now.DM++;now.op[now.num] = i;now.num++;if(now.num > 10)break;if(now.DM >= now.num – now.DM)q.push(now);}}return false;}int main() {int cas = 1;while(scanf(“%d”, &n) != EOF && n) {for(int i = 0; i < n; i++)scanf(“%d”, &num[i]);for(int i = 0; i < n; i++)scanf(“%d”, &End[i]);bool flag = true;for(int i = 0; i < n; i++)if(num[i] != End[i]) {flag = false;break;}printf(“Program %d\n”, cas++);if(flag)printf(“Empty sequence\n”);else if(!bfs())printf(“Impossible\n”);printf(“\n”);}return 0;}
最美不过偷瞄你是你忽然转头，看见你的微笑
