Atcoder ABC340 C - Divide and Divide

Divide and Divide（分而治之）

时间限制：2s 内存限制：1024MB

【原题地址】

所有图片源自Atcoder，题目译文源自脚本Atcoder Better!

点击此处跳转至原题

【问题描述】

【输入格式】

【输出格式】

【样例1】

【样例输入1】

3
1

【样例输出1】

5
1

【样例说明1】

【样例2】

【样例输入2】

340
1

【样例输出2】

2888
1

【样例3】

【样例输入3】

100000000000000000
1

【样例输出3】

5655884811924144128
1

【解题思路】

老汉使用到的是记忆递归的解题方式

本题是求将 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);
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40