louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=24594

題目大意:  能不能把寶藏分成二堆相等價值。

思路:  01背包問題，那算總和，奇數肯定無法分二堆，偶數的話就看，能不能組出一組sum/2的堆。

能組成一半一定能組成另外一半和的堆。那狀態轉移的話，就跟前面題目類似，從後面來，因為才不會蓋到左上角的陣列。

代碼:  

#include <bits/stdc++.h>
#define N 5005
using namespace std;

int arr[N];

int main()
{
    int t, k;
    cin >> t;
    while(t--){
        cin >> k;
        int sum = 0;
        for(int i = 0; i < k; ++i){
            cin >> arr[i];
            sum += arr[i];
        }
        if(sum & 1) cout << "NO\n";
        else{
            sum /= 2;
            bool dp[sum + 1] = {};
            dp[0] = 1;
            for(int i = 0; i < k; ++i){
                for(int j = sum; j >= arr[i]; --j){
                    dp[j] |= dp[j-arr[i]];
                }
            }
            puts(dp[sum] ? "YES" : "NO");
        }
    }
    return 0;
}