B. 沙漠之旅：分組背包選擇 4 桶油剛好行駛距離 L

問題描述

吉普車滿油行駛 X，後備箱最多放 4 桶油。起點有 N 種油（無限桶），第 i 種一桶行駛 A_i。問能否恰好選 4 桶油，使總行駛距離 = L（即 A_i1+A_i2+A_i3+A_i4 = L-X）。

解法：分組背包（恰好選 4 件）

這是一個「從 N 類物品中選恰好 4 件，總價值 = V」的可行性問題。用 flag[k][v] 表示選 k 件能否湊出體積 v。

DP 轉移

flag[0][0] = 1;
for (int i = 1; i <= N; ++i) {
    int d = A[i];
    for (int k = 1; k <= 4; ++k)
        for (int v = d; v <= V; ++v)
            if (flag[k-1][v-d]) flag[k][v] = 1;
}

最終檢查 `flag[4][V]`。

複雜度

• N ≤ 1000，V = L-X ≤ 1000。
• 時間 O(N × 4 × V) ≈ 4×10⁶，空間 O(5×V) ≈ 5000，極輕鬆。

關鍵代碼

int flag[5][1005];
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int L, X, N; scanf("%d%d%d", &L, &X, &N);
        int V = L - X;
        memset(flag, 0, sizeof(flag));
        flag[0][0] = 1;
        for (int i = 1; i <= N; ++i) {
            int d; scanf("%d", &d);
            for (int k = 1; k <= 4; ++k)
                for (int v = d; v <= V; ++v)
                    if (flag[k-1][v-d]) flag[k][v] = 1;
        }
        puts(flag[4][V] ? "Yes" : "No");
    }
    return 0;
}

注意：物品無限供給，但「恰好 4 件」限制使其轉化為 01 背包式的分組背包（每組最多取 1 件，共 4 組），內層循環 v 從小到大即可（因為每種油只用於當前組）。