ZeroJudge 解題筆記：a522. 12455 - Bars

作者：王一哲
日期：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")  

C++ 程式碼

用集合儲存所有可能的長度組合，使用時間約為 2 ms，記憶體約為 344 kB，通過測試。

#include <cstdio>
#include <set>
using namespace std;

int main() {
    int t; scanf("%d", &t);  // t 組測資
    while(t--) {  // 執行 t 次
        int n; scanf("%d", &n);  // 需要的長度 n
        set<int> have = {0};  // 已經有的長度集合，先放入 0
        int p; scanf("%d", &p);  // p 根金屬棒
        for(int i=0; i<p; i++) {  // 執行 p 次
            int m; scanf("%d", &m);  // 讀取金屬棒長度
            set<int> tmp;  // 暫存新的總長度
            for(int h : have) tmp.insert(h+m);  // 依序讀取已經有的長度 h，新的長度 h+m 加入 tmp
            for(int t : tmp) have.insert(t);  // tmp 的資料加入 have
        }
        if (have.count(n) == 1) puts("YES");  // 如果 n 在 have 之中印出 YES
        else puts("NO");  // 反之印出 NO
    }
    return 0;
}

用動態規劃找出所有長度可能的組合數，如果長度 $n \leq imax$ 而且組合數大於 0 印出 Yes，反之印出 No。使用時間約為 1 ms，記憶體約為 288 kB，通過測試。

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int t; scanf("%d", &t);  // t 組測資
    while(t--) {  // 執行 t 次
        int n; scanf("%d", &n);  // 需要的長度 n
        int p; scanf("%d", &p);  // p 根金屬棒
        int imax = 0;  // 所有金屬棒長度總和
        vector<int> ms (p);  // 所有金屬棒長度
        for(int i=0; i<p; i++) {  // 執行 p 次
            int m; scanf("%d", &m);  // 讀取金屬棒長度
            imax += m;
            ms[i] = m;
        }
        /* 0/1 背包問題，計自算所有長度的組合數 */
        vector<int> dp (imax + 1, 0);
        dp[0] = 1;
        for(int m : ms) {
            for(int i=imax; i>=m; i--) {
                if (dp[i-m] > 0) {
                    dp[i] += dp[i-m];
                }
            }
        }
        // 如果長度 n 小於等於 imax 而且組合數大於 0 印出 Yes
        if (n <= imax && dp[n] > 0) puts("YES");
        else puts("NO");
    }
    return 0;
}

用動態規劃及 bitset 儲存所有可能的長度組合，不記錄組合數，如果長度 $n$ 有對應的組合印出 Yes，反之印出 No。使用時間約為 1 ms，記憶體約為 44 kB，通過測試。

#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;

int main() {
    const int maxn = 2000;
    int t; scanf("%d", &t);  // t 組測資
    while(t--) {  // 執行 t 次
        int n; scanf("%d", &n);  // 需要的長度 n
        int p; scanf("%d", &p);  // p 根金屬棒
        bitset<maxn> dp;  // 所有可能的長度組合
        dp.set(0);  // 基礎狀態，有長度 0 的組合
        for(int i=0; i<p; i++) {  // 執行 p 次
            int m; scanf("%d", &m);  // 讀取金屬棒長度
            dp |= (dp << m);
        }
        // 如果有長度 n 的組合印出 Yes
        if (dp[n]) puts("YES");
        else puts("NO");
    }
    return 0;
}