b116 - TOI2008 3. 加減問題

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷給定 N 個正整數的集合，是否存在一種賦予每個數字正負號的方法，使得所有數字的和為 0。

解題思路

對於每組測試資料，首先計算所有數字的和 sum。如果 sum 是奇數，則不可能找到一種賦予正負號的方法使得和為 0，直接輸出 "No"。如果 sum 是偶數，則問題等價於判斷是否存在一個子集，其和為 sum / 2。

使用動態規劃解決子集和問題。建立一個布林陣列 b，大小為 sum / 2 + 1，初始化 b[0] 為 true，表示和為 0 的空子集存在。然後，遍歷每個數字 a[i]，如果 a[i] 小於或等於 sum / 2，則從 sum / 2 向下迭代到 a[i]，如果 b[j] 為 true，則 b[j + a[i]] 也為 true。最後，判斷 b[sum / 2] 是否為 true，如果是，則存在和為 sum / 2 的子集，輸出 "Yes"，否則輸出 "No"。

複雜度分析

• 時間複雜度: O(M * N * (sum/2))，其中 M 是測試資料組數，N 是每個測試資料的數字個數，sum 是所有數字的和。
• 空間複雜度: O(sum/2)，用於儲存動態規劃的布林陣列。

程式碼

#include <iostream>
using namespace std;
int m,n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> m >> n){
		int a[n],sum;
		while(m--){
			sum=0;
			for(int i=0;i<n;++i){
				cin >> a[i];
				sum+=a[i];
			}
			if(sum&1)
				cout << "No\n";
			else{
				sum>>=1;
				bool b[sum+1]={1};
				for(int i=0;i<n;++i){
					if(a[i]>sum)break;
					for(int j=sum-a[i];j>=0;--j)
						if(b[j]==1||j==0)
							b[j+a[i]]=1;
				}
				if(b[sum])
					cout << "Yes\n";
				else
					cout << "No\n";
			}
		}
	}
}