🔗 UVA-12455 Bars

tags: `動態規劃(DP)`

範例程式碼已於 UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定一些金屬棒，每根金屬棒的長度為 $a_i$ ，請問是否可以通過焊接（但不能剪切）這些金屬棒來得到特定長度 $target$ 的金屬棒。

每根金屬棒 只能使用一次。

若可以得到特定長度 $target$ 的金屬棒，輸出 $\text{YES}$ ；否則輸出 $\text{NO}$ 。

LuckyCat 的中文翻譯

思路：動態規劃(DP)

若在不使用第 $j$ 根金屬棒的情況下，可以通過焊接得到長度為 $i$ 的金屬棒，則可以通過焊接得到長度為 $i + a_j$ 的金屬棒，因此可以使用動態規劃(DP) 來解決。

令 $dp[i]$ 表示是否可以通過焊接得到長度為 $i$ 的金屬棒，則有以下遞迴式：

初始化 $dp[0] = \text{True}$ ，表示長度為 0 時，無需使用任何金屬棒；對於 $i \neq 0$ 的長度，初始化 $dp[i] = \text{False}$ 。
$dp[i] = \text{True}$ ，若存在 $j$ 使得 $dp[i - a_j] = \text{True}$ ，可以直接使用 or 運算符來更新 $dp[i]$ 。

但需要注意，由於每根金屬棒只能使用一次，因此在遍歷金屬棒時，需要逆序遍歷，以避免重複使用同一根金屬棒。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot \text{target})$ $O (n \cdot target)$ ，其中 $n$ $n$ 為金屬棒的數量， $\text{target}$ $target$ 為目標長度。
- 對於每個金屬棒，最多需要遍歷 $\text{target}$ 次。
空間複雜度： $\mathcal{O}(\text{target})$

T = int(input())

for _ in range(T):
    target = int(input())
    n = int(input())
    bars = list(map(int, input().split()))

    dp = [0] * (target + 1)
    dp = [False] * (target + 1)
    dp[0] = True
    for bar in bars:
        for i in range(target, bar - 1, -1):
            dp[i] |= dp[i - bar]

    print("YES" if dp[target] else "NO")

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t, target, n;
    cin >> t;
    while (t--) {
        cin >> target >> n;

        vector<int> bars(n);
        for (int i = 0; i < n; ++i) cin >> bars[i];
        vector<bool> dp(target + 1, false);

        dp[0] = true;
        for (int bar : bars) {
            for (int i = target; i >= bar; --i) {
                dp[i] = dp[i] | dp[i - bar];
            }
        }

        cout << (dp[target] ? "YES" : "NO") << endl;
    }
    return 0;
}