發表新討論
#54727: dfs解法 思路+範例


294ryan@gmail.com (Ryan)

d445. C-分堆大考驗 -- USACO | From: [163.19.6.166] | 發表日期: 2026-03-09 14:29

用DP或DFS

DFS 解的話  從最大數字N開始往下解 然後要寫記憶化 不然會TLE
​從最大的數字N 開始考慮
​每個數字i 有兩個選擇"放進 A 堆" or "放進 B 堆"
​若當前累積的和已超過sum(nums)/2 or 剩下的數字全部加起來湊不到 sum(nums)/2 ---> 直接回頭
 
sum(nums) --寫成--> N * (N + 1) // 2

import sys
def dfs(ptr, nowSum):
    global count
    if nowSum == half:
        count += 1
        return 1
   
    state = (ptr, nowSum)
    if state in memo:
        count += memo[state]
        return memo[state]
   
    remain = ptr * (ptr + 1) // 2
    if nowSum > half or ptr <= 0 or nowSum + remain < half:
        return 0
   
    # 把自己也放進去    
    temp1 = dfs(ptr-1, nowSum + ptr)
   
    # 自己不要放入
    temp2 = dfs(ptr-1, nowSum)

    res = temp1 + temp2 # Result, 暫存結果
    memo[state] = res
    return res

while True:
    try:
        N = int(input())
        nums = [i for i in range(N, 0, -1)]    # N~1

        if (N * (N + 1) // 2) % 2 == 1:    # 如果sum是奇數 則不可能分堆
            print(0)
            continue

        sys.setrecursionlimit(99999)
        half = (N * (N + 1) // 2) // 2
        got = set()
        count = 0
        memo = dict()   # 紀錄 (第幾個數字, 目前總和)

        dfs(N, 0)
        print(count // 2)
    except EOFError:
        sys.exit()
ZeroJudge Forum