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);}}