作者：王一哲
日期：2026年1月7日
ZeroJudge 題目連結：
a522. 12455 - Bars
解題想法
這題考 0/1 背包問題，由於測資不大，用 set 儲存所有可能的長度組合也能 AC，比較標準的作法是用一維陣列儲存所有長度總合的組合數，或是用 bitset 儲存所有可能的長度組合。
Python 程式碼
用集合儲存所有可能的長度組合，使用時間約為 22 ms，記憶體約為 3.3 MB，通過測試。
t = int(input()) # t 組測資
for _ in range(t): # 執行 t 次
n = int(input()) # 需要的長度 n
have = {0} # 已經有的長度集合，先放入 0
p = int(input()) # p 根金屬棒，用不到
for m in map(int, input().split()): # 讀取金屬棒長度
tmp = set() # 暫存新的總長度
for h in have: tmp.add(h+m) # 依序讀取已經有的長度 h，新的長度 h+m 加入 tmp
#for t in tmp: have.add(t) # tmp 的資料加入 have
have.update(tmp) # tmp 的資料加入 have，另一種寫法
print("YES" if n in have else "NO") # 如果 n 在 have 之中印出 YES，反之印出 NO
用動態規劃找出所有長度可能的組合數，如果長度 $n \leq imax$ 而且組合數大於 0 印出 Yes，反之印出 No。使用時間約為 10 ms，記憶體約為 2.9 MB，通過測試。
t = int(input()) # t 組測資
for _ in range(t): # 執行 t 次
n = int(input()) # 需要的長度 n
p = int(input()) # p 根金屬棒，用不到
ms = list(map(int, input().split())) # 金屬棒長度
imax = sum(ms) # 總長度
dp = [0]*(imax + 1) # 所有長度可能的組合數
dp[0] = 1 # 基礎狀態，長度 0 的組合數 1
for m in ms: # 依序讀取金屬棒長度，0/1 背包問題
for i in range(imax, m-1, -1):
if dp[i-m] > 0:
dp[i] += dp[i-m]
# 如果長度 n 小於等於 imax 而且組合數大於 0 印出 Yes
print("YES" if n <= imax and dp[n] > 0 else "NO")
用動態規劃及 bitset 儲存所有可能的長度組合，不記錄組合數，如果長度 $n$ 有對應的組合印出 Yes，反之印出 No。使用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。
t = int(input()) # t 組測資
for _ in range(t): # 執行 t 次
n = int(input()) # 需要的長度 n
p = int(input()) # p 根金屬棒，用不到
ms = list(map(int, input().split())) # 金屬棒長度
dp = 1 # 用 bitset 儲存所有可能的長度組合，基礎狀態，長度 0 的組合數 1
for m in ms: # 依序讀取金屬棒長度，0/1 背包問題
dp |= (dp << m)
# 如果長度 n 小於等於 imax 而且組合數大於 0 印出 Yes
print("YES" if (dp >> n) & 1 else "NO")
