alan23273850 的刷題筆記
b116: TOI2008 3. 加減問題
Tags: subset-sum
出處：https://zerojudge.tw/ShowProblem?problemid=b116
提交：https://zerojudge.tw/Submissions?problemid=b116&account=allllllan123456
問題：給定 $N\in[1,100]$ 個正整數，問你有沒有辦法在每個數字前面加上正號或負號使得整個式子的總和為零？
解法：此乃平分問題，是子集和問題的應用。問有沒有辦法把這些數字分成正的一堆，負的一堆，然後它們 (絕對值) 的和相等。這個動作就相當於從中挑出幾個數使得其子集和為全部和的一半。另外注意到如果全部和為奇數的話這件事情不可能成真，可以先行篩選。
附註：這題沒有限定全部數字的總和範圍，故且假設為 10000 是會 AC。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 int M, N, arr[100];
6 while (cin >> M) { cin >> N;
7 while (M--) {
8 int sum = 0; bool dp[5001] = {false}; dp[0] = true;
9 for (int i=0; i<N; i++) cin >> arr[i], sum += arr[i];
10 if (sum & 1) { cout << "No\n"; continue; }
11 for (int i=0; i<N; i++)
12 for (int j=sum/2; j>=arr[i]; j--)
13 dp[j] |= dp[j-arr[i]];
14 cout << (dp[sum/2] ? "Yes\n" : "No\n");
15 }
16 }
17 return 0;
18}