递推+高精度+找规律 UVA 10254 The Priest Mathematician-白红宇

递推+高精度+找规律 UVA 10254 The Priest Mathematician

阅读量：4973 次

发布时间：2019-06-12

本文共 2251 字，大约阅读时间需要 7 分钟。

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.cpp10  ************************************************/11 12 #include 
     
      13 #include 
      
       14 #include 
       
        15 #include 
        
         16 #include 
         
          17 #include 
          
           18 #include 
           
            19 #include 
            
             20 #include 
             
              21 #include 
              
               22 #include 
               
                23 #include 
                
                 24 #include 
                 25 #include 
                  
                   26 #include 
                   
                    27 #include 
                    
                     28 #include 
                     
                      29 using namespace std;30 31 #define lson l, mid, rt << 132 #define rson mid + 1, r, rt << 1 | 133 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("\n");76 }77 }f[10010];78 79 int main(void) { //UVA 10254 The Priest Mathematician80 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 }