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 {
// 记忆集合m
HashMap<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);
}
}
