POJ 2161 - Chandelier

http://poj.org/problem?id=2161

概要

ある形のシャンデリアの作り方を表す命令列が与えられるので、それによって作られるシャンデリアと同じ形状のものをつくり、スタックの消費量が最小となるような命令列を答える (Special Judge)。

命令列は a と数字からなり、a はペンダントを1つスタックに積むことを表し、数字はその数字の分だけスタックの上からパーツをとり、それらを順に円形にとりつけて1つのパーツにしたものを再びスタックに積むことを表している。

制約

解法

シャンデリアは根付き木の形をしている。 数字は一桁なので、各ノードには高々9個の子ノードしかない。

各ノードにおいて、自分の子ノードのうちどのノードからスタックから取り出すかを決めれば必要なスタックサイズは計算できるので、これを全部試して最小のものを選べばよい。

 1 #include <iostream>
 2 #include <deque>
 3 #include <stack>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct node
 8 {
 9   deque<const node *> c;
10   int idx;
11   int need;
12   node() : c(), idx(-1), need(1) {}
13 
14   void show() const
15   {
16     if (c.empty()) {
17       cout << 'a';
18     } else {
19       const int N = c.size();
20       for (int i = 0; i < N; i++) {
21         c[(idx+i)%N]->show();
22       }
23       cout << N;
24     }
25   }
26 };
27 
28 int main()
29 {
30   ios::sync_with_stdio(false);
31   string s;
32   cin >> s;
33   stack<node *> stk;
34   for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
35     if (*it == 'a') {
36       stk.push(new node());
37     } else {
38       const int n = *it - '0';
39       node *t = new node();
40       for (int i = 0; i < n; i++) {
41         t->c.push_front(stk.top());
42         stk.pop();
43       }
44       t->need = 100000000;
45       for (int i = 0; i < n; i++) {
46         int x = 0;
47         for (int j = 0; j < n; j++) {
48           x = max(x, t->c[(i+j)%n]->need + j);
49         }
50         if (x < t->need) {
51           t->need = x;
52           t->idx = i;
53         }
54       }
55       stk.push(t);
56     }
57   }
58   const node *root = stk.top();
59   cout << root->need << endl;
60   root->show();
61   cout << endl;
62   return 0;
63 }
poj/2161.cc