题目地址
题解
设$f(i)$为$i$个盘子时候的情况,那么当把$j$个盘子移到另一个柱子上,然后将剩下的用3根柱子汉诺塔形式移动,再将$j$个移回去时,就可以推导出$f(i)$的表达式:
其中$d(i)$为3根柱子汉诺塔中有$i$个盘子的步数。
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
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; int (){ int f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); } while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } ll d[15], f[15] = {0}; void init(){ d[1] = 1, f[1] = 1; for(int i = 2; i <= 12; ++i) d[i] = d[i - 1] << 1 | 1; } void solve(){ printf("1n"); for(int i = 2; i <= 12; ++i){ f[i] = INF; for(int j = 1; j < i; ++j) f[i] = min(f[i], (f[j] << 1) + d[i - j]); printf("%lldn", f[i]); } } int main(){ init(); solve(); return 0; }
|
近期评论