本文主要是介绍Atcoder ABC340 C - Divide and Divide，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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((n+1)/2)+n 求解答案，对于数值较小的 n 可以在规定时间内解决，但当n的值特别大时，由于过程中有许多重复计算的步骤，所花费的时间将会超出规定时间，因此老汉使用到记忆递归的方式对每次计算出来的 f(n) 的值都进行保存，减少了不必要的重复计算，使计算效率提高。
代码注释有详细过程
【代码】
package ABC340_C_DivideandDivide;import java.util.HashMap;
import java.util.Scanner;public class Main {// 记忆集合mHashMap<Long, Long> m = new HashMap<Long, 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);}}这篇关于Atcoder ABC340 C - Divide and Divide的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
