1 /*
2 题意：汉诺塔问题变形，多了第四个盘子可以放前k个塔，然后n-k个是经典的汉诺塔问题，问最少操作次数
3 递推+高精度+找规律：f[k]表示前k放在第四个盘子，g[n-k]表示经典三个盘子，2 ^ (n - k) - 1
4 所以f[n] = min (f[k] * 2 + g[n-k])，n<=10000，所要要用高精度，另外打表能看出规律
5 */
6 /************************************************
7 * Author :Running_Time
8 * Created Time :2015-8-18 9:14:21
9 * File Name :UVA_10254.cpp
10 ************************************************/
11
12 #include <cstdio>
13 #include <algorithm>
14 #include <iostream>
15 #include <sstream>
16 #include <cstring>
17 #include <cmath>
18 #include <string>
19 #include <vector>
20 #include <queue>
21 #include <deque>
22 #include <stack>
23 #include <list>
24 #include <map>
25 #include <set>
26 #include <bitset>
27 #include <cstdlib>
28 #include <ctime>
29 using namespace std;
30
31 #define lson l, mid, rt << 1
32 #define rson mid + 1, r, rt << 1 | 1
33 typedef long long ll;
34 const int MAXN = 4000 + 10;
35 const int INF = 0x3f3f3f3f;
36 const int MOD = 1e9 + 7;
37
38 struct bign {
39 short s[MAXN] , len ;
40 bign () { memset ( s ,0 , sizeof ( s ) ) ; len = 1 ; }
41 bign operator = (const char *num) {
42 len = strlen ( num ) ;
43 for ( int i = 0 ; i < len ; i ++ ) s[i] = num[len-i-1] - '0' ;
44 return *this ;
45 }
46 bign operator = (int num) {
47 char s[MAXN];
48 sprintf (s , "%d" , num);
49 *this = s ;
50 return *this ;
51 }
52 bign(const char *num) { *this = num ; }
53 bign(int num) { *this = num ; }
54 string str () const {
55 string res ;
56 res = "" ;
57 for (int i = 0; i < len; i ++) res = (char) (s[i] + '0') + res ;
58 if (res == "") res = '0';
59 return res ;
60 }
61 bign operator + (const bign& b) const {
62 bign c ;
63 c.len = 0 ;
64 for(int i = 0, g = 0; g || i < max (len, b.len); i ++) {
65 int x = g ;
66 if (i < len) x += s[i] ;
67 if (i < b.len) x += b.s[i] ;
68 c.s[c.len++] = x % 10 ;
69 g = x / 10 ;
70 }
71 return c ;
72 }
73 void print() {
74 for(int i = len - 1; i >= 0; i --) printf("%hd", s[i]);
75 printf("
");
76 }
77 }f[10010];
78
79 int main(void) { //UVA 10254 The Priest Mathematician
80 bign g = 1; f[0] = 0;
81 for (int i=1, j=1; i<=10000; j++, g=g+g) {
82 for (int k=1; k<=j && i<=10000; k++,i++) {
83 f[i] = f[i-1] + g;
84 }
85 }
86 int n;
87 while (scanf ("%d", &n) == 1) {
88 f[n].print ();
89 }
90
91 return 0;
92 }
递推+高精度+找规律 UVA 10254 The Priest Mathematician
编译人生，运行世界！