superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZOJ 1190 - Optimal Programs

Posted on 2008-05-19 15:53 superman 阅读(439) 评论(0)  编辑 收藏 引用 所属分类: ZOJ
  1 /* Accepted 1190 C++ 00:00.48 28620K */
  2 #include <iostream>
  3 
  4 using namespace std;
  5 
  6 enum { ADD = 1, DIV = 2, DUP = 3, MUL = 4, SUB = 5, maxStackSize = 11 };
  7 
  8 inline int abs(int n)
  9 {
 10     return n > 0 ? n : -n;
 11 }
 12 
 13 template <class T>
 14 class stack
 15 {
 16 public:
 17     T x[maxStackSize]; char p;
 18 
 19     stack() { p = -1; }
 20     int size() { return p + 1;}
 21     bool empty() { return p == -1; }
 22     void push(const T & item) { x[++p] = item; }
 23     void pop() { p--; }
 24     void clear() { p = -1; }
 25     T & top() { return x[p]; }
 26     
 27     void operator = (const stack & st)
 28     {
 29         memcpy(x, st.x, sizeof(st.x));
 30         p = st.p;
 31     }
 32 };
 33 
 34 struct QUEUE
 35 {
 36     int last;
 37     char cnt, op;
 38     stack <short> st;
 39 }queue[888888];
 40 
 41 string opSeq;
 42 int n, x[10], y[10];
 43 
 44 void getPath(int i)
 45 {
 46     if(queue[i].last)
 47         getPath(queue[i].last);
 48     opSeq += queue[i].op;
 49 }
 50 
 51 bool checkOthers()
 52 {
 53     for(int i = 1; i < n; i++)
 54     {
 55         stack <short> st;
 56         st.push(x[i]);
 57         int a, b;
 58         for(int k = 0; k < opSeq.size(); k++)
 59             switch(opSeq[k])
 60             {
 61                 case 1 : //ADD
 62                     a = st.top(); st.pop();
 63                     b = st.top(); st.pop();
 64                     if(abs(int(a) + int(b)) > 30000)
 65                         return false;
 66                     st.push(a + b);
 67                     break;
 68                 case 2 : //DIV
 69                     a = st.top(); st.pop();
 70                     b = st.top(); st.pop();
 71                     if(a == 0return false;
 72                     st.push(b / a);
 73                     break;
 74                 case 3 : //DUP
 75                     st.push(st.top()); break;
 76                 case 4 : //MUL
 77                     a = st.top(); st.pop();
 78                     b = st.top(); st.pop();
 79                     if(abs(int(a) * int(b)) > 30000)
 80                         return false;
 81                     st.push(a * b);
 82                     break;
 83                 case 5 : //SUB
 84                     a = st.top(); st.pop();
 85                     b = st.top(); st.pop();
 86                     if(abs(int(b) - int(a)) > 30000)
 87                         return false;
 88                     st.push(b - a);
 89                     break;
 90             }
 91         if(st.top() != y[i])
 92             return false;
 93     }
 94     return true;
 95 }
 96 
 97 int main()
 98 {
 99     int program = 0;
100     while((cin >> n) && n)
101     {
102         
103         for(int i = 0; i < n; i++)
104             cin >> x[i];
105         for(int i = 0; i < n; i++)
106             cin >> y[i];
107         
108         program++;
109         cout << "Program " << program << endl;
110         
111         bool empty_sequence = true;
112         for(int i = 0; i < n; i++)
113             if(x[i] != y[i])
114             {
115                 empty_sequence = falsebreak;
116             }
117         if(empty_sequence)
118         {
119             cout << "Empty sequence" << endl << endl; continue;
120         }
121         
122         int front = -1, rear = 0;
123         int best = INT_MAX; string bestSeq(10255);
124         bool found = false;
125         
126         queue[0].st.push(x[0]);
127         queue[0].last = 0;
128         queue[0].cnt = 0;
129         queue[0].op = 0;
130         while(front < rear)
131         {
132             front++;
133             
134             if(queue[front].cnt > best)
135                 continue;
136             
137             stack <short> st = queue[front].st;
138             
139             if(st.size() == 1 && st.top() == y[0])
140             {
141                 opSeq.clear();
142                 getPath(front);
143                 if(checkOthers())
144                 {
145                     if(queue[front].cnt == best)
146                         if(opSeq < bestSeq)
147                             bestSeq = opSeq;
148                     if(queue[front].cnt < best)
149                     {
150                         best = queue[front].cnt;
151                         bestSeq = opSeq;
152                     }
153                     found = true;
154                 }
155             }
156 
157             int a, b;
158             if(queue[front].cnt < 10)
159             {
160                 //ADD
161                 if(st.size() > 1)
162                 {
163                     rear++;
164                     queue[rear].st = st;
165                     queue[rear].op = ADD;
166                     queue[rear].cnt = queue[front].cnt + 1;
167                     queue[rear].last = front;
168                     a = queue[rear].st.top(); queue[rear].st.pop();
169                     b = queue[rear].st.top(); queue[rear].st.pop();
170                     queue[rear].st.push(a + b);
171                     if(abs(int(a) + int(b)) > 30000)
172                         rear--;
173                 }
174                 
175                 //DIV
176                 if(st.size() > 1 && st.top() != 0)
177                 {
178                     rear++;
179                     queue[rear].st = st;
180                     queue[rear].op = DIV;
181                     queue[rear].cnt = queue[front].cnt + 1;
182                     queue[rear].last = front;
183                     a = queue[rear].st.top(); queue[rear].st.pop();
184                     b = queue[rear].st.top(); queue[rear].st.pop();
185                     queue[rear].st.push(b / a);
186                 }
187                 
188                 //DUP
189                 rear++;
190                 queue[rear].st = st;
191                 queue[rear].op = DUP;
192                 queue[rear].cnt = queue[front].cnt + 1;
193                 queue[rear].last = front;
194                 queue[rear].st.push(st.top());
195                 
196                 //MUL
197                 if(st.size() > 1)
198                 {
199                     rear++;
200                     queue[rear].st = st;
201                     queue[rear].op = MUL;
202                     queue[rear].cnt = queue[front].cnt + 1;
203                     queue[rear].last = front;
204                     a = queue[rear].st.top(); queue[rear].st.pop();
205                     b = queue[rear].st.top(); queue[rear].st.pop();
206                     queue[rear].st.push(a * b);
207                     if(abs(int(a) * int(b)) > 30000)
208                         rear--;
209                 }
210                 
211                 //SUB
212                 if(st.size() > 1)
213                 {
214                     rear++;
215                     queue[rear].st = st;
216                     queue[rear].op = SUB;
217                     queue[rear].cnt = queue[front].cnt + 1;
218                     queue[rear].last = front;
219                     a = queue[rear].st.top(); queue[rear].st.pop();
220                     b = queue[rear].st.top(); queue[rear].st.pop();
221                     queue[rear].st.push(b - a);
222                     if(abs(int(b) - int(a)) > 30000)
223                         rear--;
224                 }
225             }
226         }
227 
228         if(found == false)
229             cout << "Impossible" << endl;
230         else
231             for(int i = 0; i < bestSeq.size(); i++)
232             {
233                 switch(bestSeq[i])
234                 {
235                     case 1 : cout << "ADD"break;
236                     case 2 : cout << "DIV"break;
237                     case 3 : cout << "DUP"break;
238                     case 4 : cout << "MUL"break;
239                     case 5 : cout << "SUB"break;
240                 }
241                 cout << (i == bestSeq.size() - 1 ? '\n'' ');
242             }
243         cout << endl;
244         
245         for(int i = 0; i <= rear; i++)
246             queue[i].st.clear();
247     }
248     
249     return 0;
250 }
251 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理