n个盘子摞在柱子A上, 按照下述策略移动: - 给六种操作 (AB、AC、BA、BC、CA和CB) 赋予不同的优先级. - 每次选择符合以下两个条件的操作来移动盘子, 直到所有盘子都从A移到另一根柱子: 1. 它是所有合法操作中优先级最高的. 2. 所要移动的盘子不是上一次操作所移动的.
现在给定n和每种盘子的优先级, 求游戏终止所需要的步骤数. (1≤n≤30) 看到题面这段不明觉厉的描述......我写了个暴力, 发现对于每种优先级序列, n可以用一个二阶递推来拟合. 进而发现只有3种不同的递推式. 猜出通项. 然后交了下面这段代码:
typedef long long ll;
typedef pair<int, int> P;
stack<int> a[3];
P p[6];
ll simulate(int n)
{
per (i, n, 1) a[0].push(i);
int last = -1;
ll c = 0;
while ((int)a[1].size() != n && (int)a[2].size() != n) {
rep (i, 0, 6) {
stack<int>& fr = a[p[i].first], & to = a[p[i].second];
int t;
if (p[i].first != last
&& !fr.empty()
&& (to.empty() || to.top() > fr.top())) {
t = fr.top();
fr.pop();
to.push(t);
last = p[i].second;
break;
}
}
++c;
}
return c;
}
inline ll pow3(int n)
{
ll x = 1;
while (n--) x *= 3;
return x;
}
int main()
{
int n;
scanf("%d", &n);
rep (i, 0, 6) {
char s[5];
scanf("%s", s);
p[i] = P(s[0] - 'A', s[1] - 'A');
}
ll t = simulate(3), ans;
if (t == 17)
ans = 2 * pow3(n-1) - 1;
else if (t == 9)
ans = pow3(n-1);
else
ans = (1LL<<n) - 1;
printf("%lld\n", ans);
return 0;
}看题解, 正解是递推......应该很显然的啊......TAT
设
为什么呢? 把