uva 10254——The Priest Mathematician

ゝ一纸荒年。 2022-07-28 01:35 135阅读 0赞

题意：汉诺塔题目的变形，有4根柱子，可以把顶部的k个盘子移到最后的柱子上，然后按照汉诺塔，问最后走的最小步数。

思路：递推，经过递推可以发现f[n] = f[k]*2+g[n-k]，其中f[n]为4个柱子时的最小步数，g[n]为3根柱子的最小步数。要用java大数来解决。

code：

  1. import java.math.*;
  2. import java.util.Scanner;
  4. public class Main {
  5.     public static void main(String args[]){
  7.            BigInteger f[] = new BigInteger[10010];
  8.            f[0] = BigInteger.valueOf(0);
  9.         f[1] = BigInteger.valueOf(1);
  10.         int i = 2;
  11.         int k=1;
  12.         while(i <= 10000){
  13.             BigInteger add = BigInteger.valueOf(1).shiftLeft(k);
  14.             for(int j=0; j<k+1 && i<=10000; ++j){
  15.                 f[i] = f[i-1].add(add);
  16.                 ++i;
  17.             }
  18.             ++k;
  19.         }  
  20.         Scanner cin = new Scanner(System.in);
  21.         while(cin.hasNext()){
  22.             int n = cin.nextInt();
  23.             System.out.println(f[n]);         
  24.         }
  25.     }
  26. }

发表评论

表情：
评论列表 （有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

    相关 UVA11752 The Super Powers

    最近几天的状态着实不好，数电设计的答辩不能更逗，万幸是终于到家了，看到群里有各种群赛十分开心，希望能找回刷题的动力，调整下状态。 这道题是很久前做的，细节记不太清了。。。

    深藏阁楼爱情的钟深藏阁楼爱情的钟/ 0 赞/ 132 阅读

    相关 uva 1623——Enter The Dragon

    题意：有n个装满水的湖，可以预知将来m天下雨情况，每次下满一个湖，或者不下，不下雨的时候可以让某个湖变干，问是否存在一种方案使得每次下雨之前湖总是干的。 思路：贪心

    以你之姓@以你之姓@/ 0 赞/ 284 阅读

    相关 UVA 12099 The Bookcase(dp)

    题意： 有N本书，第i本书有一个高度Hi和宽度Wi，现要求构建一个三层的书架，你必须把所有书放在书架上。设三层高度（该层最高的书的高度）之和为h，书架总宽度（即每层总宽度

    叁歲伎倆叁歲伎倆/ 0 赞/ 247 阅读