题解 | #矩形游戏#

题目链接

矩形游戏

题目描述

旺仔哥哥设计了一种"石子矩形"游戏。游戏开始时，旺仔哥哥拥有 $n$ 颗石子。一次游戏操作的流程如下：

选择一对正整数 $(r, c)$ ，满足 $r, c > 1$ 且 $r \cdot c = n$ ；
将全部石子摆放成 $r$ 行，每行恰好 $c$ 颗；
收回任意一整行石子（共 $c$ 颗），其余石子全部丢弃。

一次操作结束后，旺仔哥哥手中的石子数变为 $c$ 。随后，旺仔哥哥可在新的石子数上继续进行同样的操作。当且仅当手中仅剩 $1$ 颗石子时，游戏才会停止。

游戏得分定义为操作过程中每轮石子数的总和。给定初始石子数 $n$ ，请计算旺仔哥哥在最优策略下可以获得的最大得分。

解题思路

这是一个典型的动态规划问题。我们定义 $f(n)$ 为从 $n$ 颗石子开始游戏，能够获得的最大得分。

根据题意，一次操作将石子数从 $n$ 变为它的一个真因子 $d$ （即 $d$ 是 $n$ 的因子且 $d < n$ ）。为了让总分最大化，我们在每一步都应该做出最优选择。

状态转移方程可以这样定义： $f(n) = n + \max_{d | n, d < n} \{ f(d) \}$

其中， $d|n, d<n$ 表示 $d$ 是 $n$ 的所有真因子。这个公式的含义是：从 $n$ 开始的最大得分，等于当前石子数 $n$ 加上，从所有可能的下一个状态（即 $n$ 的所有真因子）出发所能获得的最大得分中的那个最大值。

基本情况是当石子数为 $1$ 时，游戏结束，此时得分为 $1$ 。即 $f(1) = 1$ 。

算法实现：我们可以用递归加记忆化搜索（Memoization）来实现这个动态规划。

寻找因子：对于给定的数 $n$ ，我们需要找到它的所有真因子。我们可以从 $2$ 遍历到 $\sqrt{n}$ 来寻找。
- 如果 $i$ 是 $n$ 的因子，那么 $n/i$ 也是 $n$ 的因子。
- 特别地， $1$ 总是 $n$ 的一个真因子。
递归计算：我们编写一个递归函数 solve(n) 来计算 $f(n)$ 。
- 在函数内部，我们遍历 $n$ 的所有真因子 $d$ ，并递归调用 solve(d)。
- 我们取所有 solve(d) 返回值中的最大值，与当前的 $n$ 相加，就得到了 solve(n) 的结果。
记忆化：由于在计算过程中，同一个子问题（比如 solve(12)）可能会被多次调用，为了避免重复计算，我们使用一个哈希表（如 C++ 的 std::map）来存储已经计算过的 $f(n)$ 的值。每次进入递归函数时，先检查结果是否已在哈希表中，如果是，则直接返回。

例如，计算 $f(10)$ :

$f(10) = 10 + \max(f(1), f(2), f(5))$
$f(1) = 1$
$f(2) = 2 + f(1) = 3$
$f(5) = 5 + f(1) = 6$
$f(10) = 10 + \max(1, 3, 6) = 10 + 6 = 16$

代码

c++
java
python

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;
using LL = long long;

// 使用 map 进行记忆化
map<LL, LL> memo;

// 递归函数，计算从 n 开始的最大得分
LL solve(LL n) {
    if (n == 1) {
        return 1;
    }
    // 如果已经计算过，直接返回结果
    if (memo.count(n)) {
        return memo[n];
    }

    LL max_sub_score = 0;

    // 找到 n 的所有真因子，并递归计算
    // 1 是所有数的真因子
    max_sub_score = max(max_sub_score, solve(1));

    for (LL i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            max_sub_score = max(max_sub_score, solve(i));
            max_sub_score = max(max_sub_score, solve(n / i));
        }
    }

    // 状态转移方程
    return memo[n] = n + max_sub_score;
}

int main() {
    LL n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

public class Main {
    // 使用 HashMap 进行记忆化
    private static Map<Long, Long> memo = new HashMap<>();

    // 递归函数，计算从 n 开始的最大得分
    public static long solve(long n) {
        if (n == 1) {
            return 1;
        }
        // 如果已经计算过，直接返回结果
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        long maxSubScore = 0;

        // 找到 n 的所有真因子，并递归计算
        // 1 是所有数的真因子
        maxSubScore = Math.max(maxSubScore, solve(1));
        
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                maxSubScore = Math.max(maxSubScore, solve(i));
                maxSubScore = Math.max(maxSubScore, solve(n / i));
            }
        }
        
        // 状态转移方程
        long result = n + maxSubScore;
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        System.out.println(solve(n));
    }
}

import math

# 使用字典进行记忆化
memo = {}

# 递归函数，计算从 n 开始的最大得分
def solve(n):
    if n == 1:
        return 1
    # 如果已经计算过，直接返回结果
    if n in memo:
        return memo[n]

    max_sub_score = 0
    
    # 找到 n 的所有真因子，并递归计算
    # 1 是所有数的真因子
    max_sub_score = max(max_sub_score, solve(1))

    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            max_sub_score = max(max_sub_score, solve(i))
            max_sub_score = max(max_sub_score, solve(n // i))
            
    # 状态转移方程
    memo[n] = n + max_sub_score
    return memo[n]

n = int(input())
print(solve(n))

算法及复杂度

算法：动态规划（使用递归 + 记忆化搜索）
时间复杂度： $O(\sqrt{N} \cdot k)$ ，其中 $k$ 是解决子问题所需的平均因子分解次数。由于记忆化的存在，每个子问题只会被完整计算一次。 $N$ 的因子数量远小于 $N$ 本身，因此实际运行效率很高。
空间复杂度： $O(D)$ ，其中 $D$ 是 $N$ 在递归过程中产生的所有不同子问题的数量（即所有可能遇到的因子数量），用于存储记忆化的结果。