ZeroJudge 解題筆記：d870.NOIP2000 3.乘积最大

作者：王一哲
日期：2026年8月28日


ZeroJudge 題目連結：d870.NOIP2000 3.乘积最大

解題想法

題目給字串長度 $n$、乘號數量 $k$、字串 $s$，要在 $s$ 之中加入 $k$ 個乘以，回傳乘積的最大值。這題需要用 DFS 找插入乘號的位置，並用字典或是 @lru_cache 記憶化節省時間。不過這題的字串最長為 40，乘積很大，如果用 C++ 解題要自己處理大數乘法，所以我只寫了 Python 版本。

Python 程式碼

使用時間約為 14 ms，記憶體約為 9.5 MB，通過測試。

def solve():
    import sys

    data = sys.stdin.read().split()
    n, k, s = int(data[0]), int(data[1]), data[2]

    # 記憶化 DFS
    memo = dict()
    
    def dfs(start, rem):
        # 遞迴出口，沒有乘號能加，將剩下的字串轉成整數再回傳
        if rem == 0:
            return int(s[start:])
        # 如果 memo 之中有 (start, rem)，直接回傳
        if (start, rem) in memo:
            return memo[start, rem]
        # 從 start + 1 到 n - rem 找加入乘號的位置
        imax = -1
        for i in range(start + 1, n - rem + 1):
            left_num = int(s[start : i])
            right_max = dfs(i, rem - 1)
            if right_max != -1:
                imax = max(imax, left_num * right_max)
        memo[start, rem] = imax
        return imax
    
    # 呼叫 dfs，代入起點 0，乘號的數量 k
    print(dfs(0, k))

if __name__ == "__main__":
    solve()

使用時間約為 16 ms，記憶體約為 10 MB，通過測試。

def solve():
    import sys
    from functools import lru_cache
    
    data = sys.stdin.read().split()
    if not data: return
    
    n = int(data[0])
    k = int(data[1])
    s = data[2]

    # 記憶化 DFS
    @lru_cache(maxsize = None)
    def dfs(start, rem):  # 起點，剩下的 * 數量
        # 遞迴出口，rem 等於 0，將剩下的字串轉成 int 再回傳
        if rem == 0: return int(s[start:])
        # 由 start + 1 到 n - rem 找放入 * 的位置
        imax = -1
        for i in range(start + 1, n - rem + 1):
            left_num = int(s[start : i])  # 左半邊
            right_max = dfs(i, rem - 1)  # 右半邊
            if right_max != -1:
                imax = max(imax, left_num * right_max)
        return imax

    # 呼叫 dfs，由索引值 0 開始，放入 k 個乘號
    ans = dfs(0, k)
    print(ans)

if __name__ == "__main__":
    solve()