题意分析

这段代码解决的是一个栈操作序列问题，要求找到一个由五种基本操作（ADD、DIV、DUP、MUL、SUB）组成的指令序列，使得对于给定的 n 组初始栈数据 x[i]，经过该指令序列操作后，栈顶元素变为目标值 y[i]。

约束条件：

1. 栈操作必须合法（如 ADD 需要至少两个元素，DIV 不能除零等）。
2. 所有中间计算结果必须在 [-30000, 30000] 范围内。
3. 指令序列长度不超过 10（i < 11 表示最多 10 步）。

解题思路

1. DFS 回溯搜索：

   • 枚举所有可能的指令序列（长度为 0 到 10），检查是否能将每组 x[i] 转换为 y[i]。
   • 每次尝试一种操作（ADD/DIV/DUP/MUL/SUB），模拟其对所有 n 个栈的影响。
   • 如果某次操作导致任意栈非法（如栈空、除零、溢出），则回退（rewind）并尝试其他操作。

2. 栈操作模拟：

   • ADD/DIV/MUL/SUB：弹出栈顶两个元素，计算后压入结果。
   • DUP：复制栈顶元素。
   • 每次操作记录历史（history），便于回溯时恢复栈状态。

3. 剪枝优化：

   • 一旦找到合法序列，立即终止搜索。
   • 通过 instructions 记录当前指令序列，dfs(k) 表示还需 k 步操作。

代码实现

#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

const char* commands[] = {
    "ADD", "DIV", "DUP", "MUL", "SUB"
};
const int limit = 30000;

int n, x[10], y[10];
vector<int> stack[10], instructions, history[10];

void print()
{
    if(instructions.empty()){
        puts("Empty sequence");
        return;
    }
    printf("%s", commands[instructions[0]]);
    for(int i = 1; i < instructions.size(); ++i) printf(" %s", commands[instructions[i]]);
    puts("");
}
bool add(vector<int>& v, vector<int>& h)
{
    int n = v.size(), r;
    if(n < 2) return false;
    r = v[n-1] + v[n-2];
    if(abs(r) > limit) return false;
    h.push_back(v[n-1]);
    h.push_back(v[n-2]);
    v.pop_back();
    v.back() = r;
    return true;
}
bool div(vector<int>& v, vector<int>& h)
{
    int n = v.size(), r;
    if(n < 2) return false;
    if(v.back() == 0) return false;
    r = v[n-2] / v[n-1];
    if(abs(r) > limit) return false;
    h.push_back(v[n-1]);
    h.push_back(v[n-2]);
    v.pop_back();
    v.back() = r;
    return true;
}
bool dup(vector<int>& v, vector<int>& h)
{
    int n = v.size(), r;
    if(n < 1) return false;
    v.push_back(v.back());
    return true;
}
bool mul(vector<int>& v, vector<int>& h)
{
    int n = v.size(), r;
    if(n < 2) return false;
    r = v[n-1] * v[n-2];
    if(abs(r) > limit) return false;
    h.push_back(v[n-1]);
    h.push_back(v[n-2]);
    v.pop_back();
    v.back() = r;
    return true;
}
bool sub(vector<int>& v, vector<int>& h)
{
    int n = v.size(), r;
    if(n < 2) return false;
    r = v[n-2] - v[n-1];
    if(abs(r) > limit) return false;
    h.push_back(v[n-1]);
    h.push_back(v[n-2]);
    v.pop_back();
    v.back() = r;
    return true;
}
bool simulate(int i, int j)
{
    switch(i){
        case 0: return add(stack[j], history[j]);
        case 1: return div(stack[j], history[j]);
        case 2: return dup(stack[j], history[j]);
        case 3: return mul(stack[j], history[j]);
        default: return sub(stack[j], history[j]);
    }
}
void rewind(int i, int j)
{
    if(i == 2) stack[j].pop_back();
    else{
        stack[j].back() = history[j].back(); history[j].pop_back();
        stack[j].push_back(history[j].back()); history[j].pop_back();
    }
}
bool dfs(int k)
{
    if(!k){
        for(int i = 0; i < n; ++i){
            if(!(stack[i].size() == 1 && stack[i][0] == y[i])) return false;
        }
        return true;
    }

    int i, j;
    for(i = 0; i < 5; ++i){
        for(j = 0; j < n; ++j){
            if(!simulate(i, j)) break;
        }
        if(j < n){
            for(--j; j > -1; --j) rewind(i, j);
            continue;
        }
        instructions.push_back(i);
        if(dfs(k - 1)) return true;
        for(--j; j > -1; --j) rewind(i, j);
        instructions.pop_back();
    }
    return false;
}

int main()
{
    int t = 0, i, j;
    while(scanf("%d", &n), n){
        for(i = 0; i < n; ++i) scanf("%d", x + i);
        for(i = 0; i < n; ++i) scanf("%d", y + i);
        printf("Program %d\n", ++t);
        instructions.clear();
        for(i = 0; i < 11; ++i){
            for(j = 0; j < n; ++j){
                stack[j].clear();
                stack[j].push_back(x[j]);
            }
            if(dfs(i)) break;
        }
        if(i < 11) print(), puts("");
        else puts("Impossible\n");
    }
    return 0;
}