HDU_1207

题目链接

• 点此跳转

方法

设 $f[n]$ 为使用 $4$ 个柱子时，将 $n$ 个盘子移动到 $3$ 号柱子的花费。

首先将当前柱子上的前 $x$ 个盘子移动到 $3$ 号柱子上 ，花费为 $f[x]$ ，其中 $1\le x<n$ ，枚举即可。

剩余的盘子移动到 $4$ 号柱子上，由于只能使用 $3$ 个柱子，转化为初始汉诺塔问题，花费为 $2^{n-x}-1$ （原汉诺塔问题结论）。

再将第 $4$ 个柱子上的盘子移回 $3$ 号柱子，花费为 $f[x]$ 。

∴ f [ i ] = m i n { 2 × f [ x ] + 2 n − x − 1 , 1 ≤ x < n } \therefore f[i] = min\{2\times f[x] + 2^{n-x}-1, 1\le x∴f[i]=min{2×f[x]+2n−x−1,1≤x<n}

其中 $f[1]=1$ 。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define endl '\n'
#define PI acos(-1)
#define LL long long
#define INF 0x3f3f3f3f
#define lowbit(x) (-x&x)
#define mem(a, b) memset(a, b, sizeof a)
#define rev(x) reverse(x.begin(), x.end())
#define IOS ios::sync_with_stdio(false),cin.tie(0)

using namespace std;

const int N = 100;

int f[N];
int n;

void init() {
	f[1] = 1;
	for (int i = 2; i <= 64; i ++ ) {
		int tmp = INF;
		for (int j = 1; j < i; j ++ ) {
			tmp = min((double)tmp, (double)f[j] * 2 + pow(2, i - j) - 1);
		}
		f[i] = tmp;
	}
}

void solve() {
	init();
	
	while (cin >> n) {
		cout << f[n] << endl;
	}
}

int main() {
	IOS;
	
	solve();
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61