UVA 12455 - Bars

題目:

我們有一些已知長度的金屬棒，請問可以找出所需的特定長度的金屬棒嗎？必要時，可以把幾根金屬棒焊接成更長的一根，但金屬棒不得切割。

Input
輸入的第一行含有一個整數 𝑡, 0 ≤ 𝑡 ≤ 50，表示測資的筆數。每筆測資三行，第一行有一個數字 𝑛, 0 ≤ 𝑛 ≤ 1000，表示我們所要的長度。第二行有一個數字 𝑝, 1 ≤ 𝑝 ≤ 20，表示我們所擁有的金屬棒的數量。第三行有 𝑝 個數字，表示 𝑝 根金屬棒的長度。

Output
每筆測資輸出一行，依是否可能成功輸出「YES」或「NO」字串。

Sample Input #1
4
25
4
10 12 5 7
925
10
45 15 120 500 235 58 6 12 175 70
120
5
25 25 25 25 25
0
2
13 567

Sample Output #1
NO
YES
NO
YES

C++ code:
**DP**

#include <bits/stdc++.h>

using namespace std;

bool cmp(int n, vector<int> &len) {

    int m = len.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

    for (int i = 0; i <= m; ++i) {
        dp[i][0] = true;
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= len[i - 1]) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - len[i - 1]];
            }
        }
    }
    return dp[m][n];
    
}

int main() {

    int t;
    cin >> t;
    while (t--) {

        int n, p;
        cin >> n >> p;
        vector<int> len(p);
        for (int i = 0; i < p; ++i) {
            cin >> len[i];
        }
        if (cmp(n, len)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }

    }

    return 0;
}