AcWing 96. 奇怪的汉诺塔
原题链接
简单
作者:
dajianer
,
2021-05-19 23:32:07
,
所有人可见
,
阅读 308
P16 递推
状态定义
- d[i]表示将i个盘在3坐塔的情况下移动的最小步数
- f[i]表示将i个盘在4坐塔的情况下移动的最小步数
状态转移
- d[i] = d[i-1]*2 + 1
表示将i-1个盘移动到C,再将第i个盘移动到B,最后将n-1个盘移动到B
- f[i] = f[j]*2 + d[i-j]
表示将j个盘移动到D,再将剩余的i-j个盘在3塔的情况下移动到C,最后将j个盘移动到C
1 <= j < i
#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
signed main() {
int n = 12;
int f[15];
int d[15];
d[1] = 1;
for (int i = 2; i <= 12; i++) {
d[i] = 2*d[i-1] + 1;
}
memset(f, INF, sizeof f);
f[1] = 1;
cout << 1 << "\n";
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
f[i] = min(f[i], f[j]*2 + d[i - j]);
}
cout << f[i] << "\n";
}
}