d512 - 創造數字

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算從給定的 N 個數字中，通過任意組合相加可以產生多少種不同的數字。輸入包含 N，以及接下來的 N 個數字。

解題思路

這題的核心思想是利用集合(set)來儲存所有可以產生的數字。程式碼從 0 開始，迭代輸入的每個數字 k。對於集合中已有的每個數字，將其加上 k，並將結果插入集合。由於 set 的特性，重複的數字只會儲存一次，因此最終 set 的大小減 1 (因為初始時有 0) 就是不同數字的數量。 這種方法實際上是一種動態規劃的迭代實現，每次迭代都擴充了可以達成的數字集合。

複雜度分析

• 時間複雜度: O(N * S)，其中 N 是輸入數字的個數，S 是最終 set 的大小。在最壞情況下，S 可能接近 2^N，但題目限制了 sigma(Number) ≦ 2^31 - 1，且答案小於 10萬，所以實際運行時間在可接受範圍內。
• 空間複雜度: O(S)，其中 S 是最終 set 的大小，用於儲存所有不同的數字。

程式碼

#include <iostream>
#include <set>
using namespace std;
long long n,k;
set <long long> :: iterator it;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		set <long long> s={0};
		for(int i=0;i<n;++i){
			cin >> k;
			for(it=s.end();*it;){
				--it;
				s.insert(*it+k);
			}
		} 
		cout << s.size()-1 << "\n";
 	}
}