UVA - 656 Optimal Programs
7936 ワード
2つのシーケンスを与えて、1つの関数f(x)=yを探し出して、xiとyiはそれぞれ2つのシーケンスの中のi番目の要素に対応して、関数の操作手順を出力して、最も短くて、しかも辞書の順序に従って出力します.解題構想:x 0からy 0までの可能なステップを再帰的に列挙し、他がすべて満たされているかどうかを判断する.
#include <cstdio>
#include <stack>
#include <cmath>
using namespace std;
int T, n, ans, start[15], end[15], rec[20], path[20];
char str[5][5] = {"ADD", "DIV", "DUP", "MUL", "SUB"};
stack <int> S;
void init() {
ans = 11;
for (int i = 0; i < n; i++)
scanf("%d", &start[i]);
for (int i = 0; i < n; i++)
scanf("%d", &end[i]);
}
bool judge(int cur) {
for (int i = 1; i < n; i++) {
stack <int> SS;
SS.push(start[i]);
for (int j = 0; j < cur; j++) {
int a = SS.top(), b;
if (abs(a) > 30000 || (rec[j] == 1 && a == 0))
return false;
if (rec[j] != 2) {
SS.pop();
b = SS.top();
SS.pop();
}
switch (rec[j]) {
case 0: SS.push(a + b); break;
case 1: SS.push(b / a); break;
case 2: SS.push(a); break;
case 3: SS.push(a * b); break;
case 4: SS.push(b - a); break;
}
}
if (SS.top() != end[i])
return false;
}
return true;
}
void DFS(int cur, int DUP) {
if (S.top() == end[0] && ans > cur && judge(cur)) {
ans = cur;
for (int i = 0; i < cur; i++)
path[i] = rec[i];
return;
}
if (cur == ans - 1 || abs(S.top()) > 30000)
return;
if (S.size() > 1) {
int a = S.top(); S.pop();
int b = S.top(); S.pop();
rec[cur] = 0;
S.push(a + b);
DFS(cur + 1, DUP);
S.pop();
if (a != 0) {
rec[cur] = 1;
S.push(b / a);
DFS(cur + 1, DUP);
S.pop();
}
S.push(b);
S.push(a);
}
if (DUP < 5) {
rec[cur] = 2;
S.push(S.top());
DFS(cur + 1, DUP + 1);
S.pop();
}
if (S.size() > 1) {
int a = S.top(); S.pop();
int b = S.top(); S.pop();
rec[cur] = 3;
S.push(a * b);
DFS(cur + 1, DUP);
S.pop();
rec[cur] = 4;
S.push(b - a);
DFS(cur + 1, DUP);
S.pop();
S.push(b);
S.push(a);
}
}
void put() {
printf("Program %d
", ++T);
if (ans == 0)
puts("Empty sequence
");
else if (ans == 11)
puts("Impossible
");
else {
for (int i = 0; i < ans - 1; i++)
printf("%s ", str[path[i]]);
printf("%s
", str[path[ans-1]]);
}
}
int main() {
while (scanf("%d", &n), n) {
init();
S.push(start[0]);
DFS(0, 0);
S.pop();
put();
}
return 0;
}