企业网站建站 广州 视频,写字楼租赁,树莓派做网站服务器怎样,长沙网络推广小公司Divide and Divide#xff08;分而治之#xff09;
时间限制#xff1a;2s 内存限制#xff1a;1024MB
【原题地址】
所有图片源自Atcoder#xff0c;题目译文源自脚本Atcoder Better!
点击此处跳转至原题
【问题描述】 【输入格式】 【输出格式】 【样例1】
【样例…Divide and Divide分而治之
时间限制2s 内存限制1024MB
【原题地址】
所有图片源自Atcoder题目译文源自脚本Atcoder Better!
点击此处跳转至原题
【问题描述】 【输入格式】 【输出格式】 【样例1】
【样例输入1】
3【样例输出1】
5【样例说明1】 【样例2】
【样例输入2】
340【样例输出2】
2888【样例3】
【样例输入3】
100000000000000000【样例输出3】
5655884811924144128【解题思路】
老汉使用到的是记忆递归的解题方式
本题是求将 n 分解至 n 个 1 所花费的金额。 如果单纯的使用关系式 f(n)f(n/2)f((n1)/2)n 求解答案对于数值较小的 n 可以在规定时间内解决但当n的值特别大时由于过程中有许多重复计算的步骤所花费的时间将会超出规定时间因此老汉使用到记忆递归的方式对每次计算出来的 f(n) 的值都进行保存减少了不必要的重复计算使计算效率提高。
代码注释有详细过程
【代码】
package ABC340_C_DivideandDivide;import java.util.HashMap;
import java.util.Scanner;public class Main {// 记忆集合mHashMapLong, Long m new HashMapLong, Long();public static void main(String[] args) {Scanner scan new Scanner(System.in);long n scan.nextLong();Main ma new Main();System.out.println(ma.divide(n));scan.close();}/*** 使用记忆递归保存每一步求值结果减少重复计算缩短计算时间* * param n 所要求值的数* return 所需支付的总金额*/public long divide(long n) {// 当n为1时无需再进行计算if (n 1) {return 0;}// 当记忆集合m中存有对应值时直接调用该对应结果else if (m.get(n) ! null) {return m.get(n);}// 当记忆集合中不存在对应值利用关系式进行计算存储m.put(n, divide(n / 2) divide((n 1) / 2) n);// 放回计算后得出的结果return m.get(n);}}
