UVA 10254-The Priest Mathematician(大数+递推)
发布时间:2020-12-14 02:38:41 所属栏目:大数据 来源:网络整理
导读:题目大意:在原本的汉诺塔游戏基础上加一根柱子,移动策略是:要移动N个汉诺塔,先用4根柱子把K个到一个柱子,然后用其余3根把剩下的N-K个移动到目标柱子,再用4根把初始的K个移动到目标柱子。 关键的问题是找到每个N的K是多少,观察可以发现规律是:随着K的
题目大意:在原本的汉诺塔游戏基础上加一根柱子,移动策略是:要移动N个汉诺塔,先用4根柱子把K个到一个柱子,然后用其余3根把剩下的N-K个移动到目标柱子,再用4根把初始的K个移动到目标柱子。 关键的问题是找到每个N的K是多少,观察可以发现规律是:随着K的递增,其实移动的次数Fn(K)先递增后递减,然后F1(K),F2(K),...的最大值随着K的增大递增。要形式化证明似乎比较困难。。不过在题目的范围内这是可以AC的。程序中维护这个当前使得Fi(K)最大的K,然后递推。 import java.util.*; import java.math.*; public class Main{ public static void main(String[] args){ Scanner input=new Scanner(System.in); int u,n; final BigInteger TWO=new BigInteger("2"); BigInteger[] a=new BigInteger[210]; BigInteger[] d=new BigInteger[10010]; BigInteger minp; a[0]=BigInteger.ZERO; for(int i=1;i<=200;i++){ a[i]=a[i-1].multiply(TWO).add(BigInteger.ONE); } d[0]=BigInteger.ZERO; d[1]=BigInteger.ONE; d[2]=new BigInteger("3"); u=1; for(int i=3;i<=10000;i++){ minp=d[u].multiply(TWO).add(a[i-u]); while((u<i-1)&&(minp.compareTo(d[u+1].multiply(TWO).add(a[i-u-1]))>0)){ minp=d[u+1].multiply(TWO).add(a[i-u-1]); u++; } d[i]=minp; } while(input.hasNext()){ n=input.nextInt(); System.out.println(d[n]); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |